426
13 L’ordinateur ` a ADN
`
A premi` ere vue, il peut sembler difficile de r´ ealiser des op´ erations num´ eriques avec
une machine de Turing. Cependant, ces machines permettent de travailler sur des fonctions ayant comme entr´ ees des nombres naturels. Nous utilisons la repr´ esentation unaire
des nombres.
D´ efinition 13.6 Un nombre x ∈ N a pour repr´ esentation unaire 1
x+1 , c’est-` a-dire la
concat´ enation de x + 1 symboles 1. Ainsi, la repr´ esentation unaire de 0 est 1, celle de 1
est 11, celle de 2 est 111, etc. La repr´ esentation unaire d’un nombre x est not´ ee par x .
Exemple 13.7 (la fonction successeur) Nous pouvons construire une machine de
Turing qui effectue la fonction successeur d´ efinie comme suit : s(x) = x + 1. L’alphabet de ruban est X = {1, B}, l’alphabet d’´ etat est Q = {q 0 , q 1 , q 2 }, Q f = {q 2 },
U = {λ, B1B, B11B, B111B, . . .}, et la fonction ϕ est donn´ ee `
a la figure 13.6. Notons
que l’entr´ ee sur le ruban est la repr´ esentation unaire d’un nombre pr´ ec´ ed´ ee par le symbole B. Toutes les autres cases du ruban sont occup´ ees par le symbole B.
Fig. 13.6. Fonction successeur
Le pointeur rencontre tout d’abord un blanc ; il change d’´ etat et se dirige vers la droite
jusqu’` a ce qu’il rencontre un deuxi` eme blanc. Le blanc est remplac´ e par un 1, et le
pointeur se dirige vers la gauche jusqu’` a ce qu’il rencontre de nouveau le premier blanc.
La machine s’arrˆ ete alors puisque ϕ(q 2 , B) n’est pas d´ efinie.
Exemple 13.8 (la fonction z´ ero) Construisons une machine permettant d’effectuer
la fonction z´ ero d´ efinie comme suit : z(x) = 0. Nous devons effacer tous les 1 sauf
le premier et retourner au premier blanc. L’alphabet de ruban est le mˆ eme que dans
l’exemple pr´ ec´ edent, et l’alphabet d’´ etat est Q = {q 0 , q 1 , q 2 , q 3 , q 4 }. La configuration
initiale du ruban est q 0 BxB, et la configuration finale est q f B1B (ici q f = q 4 ). La
fonction ϕ est repr´ esent´ ee ` a la figure 13.7.
Exemple 13.9 (l’addition) Nous allons maintenant construire une machine de Turing qui effectue une addition. Sur le ruban, on marque comme entr´ ee BxByB, o` u x et
y sont les deux nombres ` a additionner (dans leur repr´ esentation unaire). La machine
changera le blanc entre les deux nombres `
a additionner pour un 1, puis effacera les deux
derniers 1 rencontr´ es. La configuration finale sera q f Bx + yB, avec q f = q 5 . L’alphabet
d’´ etat est Q = {q i : i = 0, . . . , 5}. L’alphabet de ruban reste celui de l’exemple pr´ ec´ edent.
La fonction ϕ est d´ ecrite ` a la figure 13.8.
13 L’ordinateur ` a ADN
`
A premi` ere vue, il peut sembler difficile de r´ ealiser des op´ erations num´ eriques avec
une machine de Turing. Cependant, ces machines permettent de travailler sur des fonctions ayant comme entr´ ees des nombres naturels. Nous utilisons la repr´ esentation unaire
des nombres.
D´ efinition 13.6 Un nombre x ∈ N a pour repr´ esentation unaire 1
x+1 , c’est-` a-dire la
concat´ enation de x + 1 symboles 1. Ainsi, la repr´ esentation unaire de 0 est 1, celle de 1
est 11, celle de 2 est 111, etc. La repr´ esentation unaire d’un nombre x est not´ ee par x .
Exemple 13.7 (la fonction successeur) Nous pouvons construire une machine de
Turing qui effectue la fonction successeur d´ efinie comme suit : s(x) = x + 1. L’alphabet de ruban est X = {1, B}, l’alphabet d’´ etat est Q = {q 0 , q 1 , q 2 }, Q f = {q 2 },
U = {λ, B1B, B11B, B111B, . . .}, et la fonction ϕ est donn´ ee `
a la figure 13.6. Notons
que l’entr´ ee sur le ruban est la repr´ esentation unaire d’un nombre pr´ ec´ ed´ ee par le symbole B. Toutes les autres cases du ruban sont occup´ ees par le symbole B.
Fig. 13.6. Fonction successeur
Le pointeur rencontre tout d’abord un blanc ; il change d’´ etat et se dirige vers la droite
jusqu’` a ce qu’il rencontre un deuxi` eme blanc. Le blanc est remplac´ e par un 1, et le
pointeur se dirige vers la gauche jusqu’` a ce qu’il rencontre de nouveau le premier blanc.
La machine s’arrˆ ete alors puisque ϕ(q 2 , B) n’est pas d´ efinie.
Exemple 13.8 (la fonction z´ ero) Construisons une machine permettant d’effectuer
la fonction z´ ero d´ efinie comme suit : z(x) = 0. Nous devons effacer tous les 1 sauf
le premier et retourner au premier blanc. L’alphabet de ruban est le mˆ eme que dans
l’exemple pr´ ec´ edent, et l’alphabet d’´ etat est Q = {q 0 , q 1 , q 2 , q 3 , q 4 }. La configuration
initiale du ruban est q 0 BxB, et la configuration finale est q f B1B (ici q f = q 4 ). La
fonction ϕ est repr´ esent´ ee ` a la figure 13.7.
Exemple 13.9 (l’addition) Nous allons maintenant construire une machine de Turing qui effectue une addition. Sur le ruban, on marque comme entr´ ee BxByB, o` u x et
y sont les deux nombres ` a additionner (dans leur repr´ esentation unaire). La machine
changera le blanc entre les deux nombres `
a additionner pour un 1, puis effacera les deux
derniers 1 rencontr´ es. La configuration finale sera q f Bx + yB, avec q f = q 5 . L’alphabet
d’´ etat est Q = {q i : i = 0, . . . , 5}. L’alphabet de ruban reste celui de l’exemple pr´ ec´ edent.
La fonction ϕ est d´ ecrite ` a la figure 13.8.