434
13 L’ordinateur ` a ADN
4. On efface les n premiers nombres en les rempla¸ cant par des B et on translate les
nombres restants, comme il est demand´ e dans l’exercice 3, pour obtenir la configuration
Bg 1 (x 1 , . . . , x n )B . . . Bg k (x 1 , . . . , x n )B.
5. La machine H effectue l’op´ eration finale. On obtient alors
Bh(y 1 , . . . , y k )B,
o` u y i = g i (x 1 , . . . , x n ), qui est effectivement
Bf (x 1 , . . . , x n )B.
Montrons maintenant la fermeture sous la r´ ecurrence. Soient g et h des fonctions
arithm´ etiques calculables par une machine de Turing et soit f la fonction
f (x 1 , . . . , x n , 0) = g(x 1 , . . . , x n )
f (x 1 , . . . , x n , y + 1) = h(x 1 , . . . , x n , y, f(x 1 , . . . , x n , y))
d´ efinie par r´ ecurrence de base g et de pas h. Soient G et H des machines de Turing
standard qui permettent de calculer les fonctions g et h respectivement.
1. Le calcul de f (x 1 , . . . , x n , y) commence avec la configuration de ruban
Bx 1 Bx 2 B . . . Bx n ByB.
2. Un compteur qui d´ ebute `
a z´ ero est plac´ e ` a la droite des entr´ ees et de la variable de
r´ ecursion y. Ce compteur permet d’enregistrer la valeur de la variable r´ ecursive tout
au long des calculs. Les nombres x 1 , . . . , x n sont r´ ep´ et´ es ` a la droite du compteur, ce
qui produit la configuration
Bx 1 Bx 2 B . . . Bx n ByB0Bx 1 Bx 2 B . . . Bx n B.
3. La machine G effectue le calcul de g(x 1 , . . . , x n ) sur les n derni` eres valeurs du ruban,
produisant
Bx 1 Bx 2 B . . . Bx n ByB0Bg(x 1 , . . . , x n )B.
Notons ici que le nombre g(x 1 , . . . , x n ) est ´ egal `
a f (x 1 , . . . , x n , 0).
4. Le ruban a maintenant la forme
Bx 1 Bx 2 B . . . Bx n ByBiBf (x 1 , . . . , x n , i)B,
o` u i = 0. Les op´ erations effectu´ ees pour i = 0 ´ etant identiques `
a celles que l’on
effectuera plus tard pour les autres valeurs de i, on d´ ecrit directement le cas g´ en´ eral.
13 L’ordinateur ` a ADN
4. On efface les n premiers nombres en les rempla¸ cant par des B et on translate les
nombres restants, comme il est demand´ e dans l’exercice 3, pour obtenir la configuration
Bg 1 (x 1 , . . . , x n )B . . . Bg k (x 1 , . . . , x n )B.
5. La machine H effectue l’op´ eration finale. On obtient alors
Bh(y 1 , . . . , y k )B,
o` u y i = g i (x 1 , . . . , x n ), qui est effectivement
Bf (x 1 , . . . , x n )B.
Montrons maintenant la fermeture sous la r´ ecurrence. Soient g et h des fonctions
arithm´ etiques calculables par une machine de Turing et soit f la fonction
f (x 1 , . . . , x n , 0) = g(x 1 , . . . , x n )
f (x 1 , . . . , x n , y + 1) = h(x 1 , . . . , x n , y, f(x 1 , . . . , x n , y))
d´ efinie par r´ ecurrence de base g et de pas h. Soient G et H des machines de Turing
standard qui permettent de calculer les fonctions g et h respectivement.
1. Le calcul de f (x 1 , . . . , x n , y) commence avec la configuration de ruban
Bx 1 Bx 2 B . . . Bx n ByB.
2. Un compteur qui d´ ebute `
a z´ ero est plac´ e ` a la droite des entr´ ees et de la variable de
r´ ecursion y. Ce compteur permet d’enregistrer la valeur de la variable r´ ecursive tout
au long des calculs. Les nombres x 1 , . . . , x n sont r´ ep´ et´ es ` a la droite du compteur, ce
qui produit la configuration
Bx 1 Bx 2 B . . . Bx n ByB0Bx 1 Bx 2 B . . . Bx n B.
3. La machine G effectue le calcul de g(x 1 , . . . , x n ) sur les n derni` eres valeurs du ruban,
produisant
Bx 1 Bx 2 B . . . Bx n ByB0Bg(x 1 , . . . , x n )B.
Notons ici que le nombre g(x 1 , . . . , x n ) est ´ egal `
a f (x 1 , . . . , x n , 0).
4. Le ruban a maintenant la forme
Bx 1 Bx 2 B . . . Bx n ByBiBf (x 1 , . . . , x n , i)B,
o` u i = 0. Les op´ erations effectu´ ees pour i = 0 ´ etant identiques `
a celles que l’on
effectuera plus tard pour les autres valeurs de i, on d´ ecrit directement le cas g´ en´ eral.