454
13 L’ordinateur ` a ADN
Ce brin pourra alors ˆ etre compl´ et´ e par l’ADN polym´ erase. On voit ici comment les brins
dans lesquels un seul des deux sommets 0 ou 6 est pr´ esent se r´ epliquent plus lentement
que les brins contenant les deux sommets.
Ce cycle de refroidissement (r´ eaction de l’ADN polym´ erase avec des amorces) et de
r´ echauffement (s´ eparation des brins des mol´ ecules d’ADN) fait croˆ ıtre exponentiellement
le nombre de mol´ ecules poss´ edant le bon sommet de d´ epart et le bon sommet d’arriv´ ee
(il double `
a chaque ´ etape du cycle), tandis que le nombre de celles qui n’ont ni le bon
d´ ebut ni la bonne fin reste toujours le mˆ eme. Les mol´ ecules qui ont soit le bon d´ epart,
soit la bonne fin, mais pas les deux, se reproduisent aussi, mais ` a un rythme beaucoup
plus lent que celles qui nous int´ eressent, comme nous avons pu voir dans l’exemple 13.47.
En fin de compte, apr` es n applications de ce cycle, il y a plus de 2
n brins sommet
tronqu´ es et brins arˆ ete pour chacun des chemins commen¸ cant par un sommet 0 et se
terminant par un sommet 6. Parmi cette multitude, on esp` ere que, si n est assez grand, le
nombre de mol´ ecules qui r´ epondent `
a notre premier crit` ere soit suffisamment important
pour qu’on puisse les trouver en appliquant les autres ´ etapes de la m´ ethode d’Adleman.
13.7 Exercices
Les machines de Turing
1. Soient la figure 13.11 repr´ esentant la fonction ϕ d’une machine de Turing M et
l’entr´ ee
B111111B11111B11111B11B.
Le pointeur se trouve sur le B le plus ` a gauche au d´ epart. D´ ecrire l’action de la
machine et pr´ eciser quelle est la position du pointeur ` a la fin du calcul de M. Notons
que l’action ne change pas n´ ecessairement l’entr´ ee.
Fig. 13.11. La fonction ϕ de l’exercice 1
2. a) Construire une machine de Turing permettant de recopier un nombre unaire `
a
sa suite en laissant un blanc entre les deux (l’entr´ ee est BxB et la sortie BxBxB).
Ne pas oublier de ramener le pointeur avant le premier nombre.
b) Construire une machine de Turing permettant de copier k fois un nombre
unaire, les k copies du nombre ´ etant s´ epar´ ees par des blancs. Utiliser l’induction.
13 L’ordinateur ` a ADN
Ce brin pourra alors ˆ etre compl´ et´ e par l’ADN polym´ erase. On voit ici comment les brins
dans lesquels un seul des deux sommets 0 ou 6 est pr´ esent se r´ epliquent plus lentement
que les brins contenant les deux sommets.
Ce cycle de refroidissement (r´ eaction de l’ADN polym´ erase avec des amorces) et de
r´ echauffement (s´ eparation des brins des mol´ ecules d’ADN) fait croˆ ıtre exponentiellement
le nombre de mol´ ecules poss´ edant le bon sommet de d´ epart et le bon sommet d’arriv´ ee
(il double `
a chaque ´ etape du cycle), tandis que le nombre de celles qui n’ont ni le bon
d´ ebut ni la bonne fin reste toujours le mˆ eme. Les mol´ ecules qui ont soit le bon d´ epart,
soit la bonne fin, mais pas les deux, se reproduisent aussi, mais ` a un rythme beaucoup
plus lent que celles qui nous int´ eressent, comme nous avons pu voir dans l’exemple 13.47.
En fin de compte, apr` es n applications de ce cycle, il y a plus de 2
n brins sommet
tronqu´ es et brins arˆ ete pour chacun des chemins commen¸ cant par un sommet 0 et se
terminant par un sommet 6. Parmi cette multitude, on esp` ere que, si n est assez grand, le
nombre de mol´ ecules qui r´ epondent `
a notre premier crit` ere soit suffisamment important
pour qu’on puisse les trouver en appliquant les autres ´ etapes de la m´ ethode d’Adleman.
13.7 Exercices
Les machines de Turing
1. Soient la figure 13.11 repr´ esentant la fonction ϕ d’une machine de Turing M et
l’entr´ ee
B111111B11111B11111B11B.
Le pointeur se trouve sur le B le plus ` a gauche au d´ epart. D´ ecrire l’action de la
machine et pr´ eciser quelle est la position du pointeur ` a la fin du calcul de M. Notons
que l’action ne change pas n´ ecessairement l’entr´ ee.
Fig. 13.11. La fonction ϕ de l’exercice 1
2. a) Construire une machine de Turing permettant de recopier un nombre unaire `
a
sa suite en laissant un blanc entre les deux (l’entr´ ee est BxB et la sortie BxBxB).
Ne pas oublier de ramener le pointeur avant le premier nombre.
b) Construire une machine de Turing permettant de copier k fois un nombre
unaire, les k copies du nombre ´ etant s´ epar´ ees par des blancs. Utiliser l’induction.