424
13 L’ordinateur ` a ADN
Bq 2 01100B
q 2 B01100B
Nous avons atteint la position finale. En effet, aucun mouvement n’est pr´ evu lorsque
la machine est dans l’´ etat q 2 et pointe vers un B. Donc, elle est forc´ ee de s’arrˆ eter, et
nous avons le r´ esultat escompt´ e.
Nous voyons ` a pr´ esent l’utilit´ e des diff´ erents ´ etats : pour un mˆ eme symbole, l’op´ eration effectu´ ee par la machine et la direction dans laquelle elle se d´ eplace d´ ependent de
l’´ etat dans lequel elle se trouve. On voit aussi pourquoi il ne faut pas changer d’´ etat si
on r´ ep` ete toujours la mˆ eme op´ eration. Cela permet `
a la machine, qui a un nombre fini
d’instructions de traiter un nombre arbitrairement grand d’entr´ ees 0 et 1 entre les deux
symboles B.
Nous pouvons maintenant d´ efinir plus rigoureusement ce qu’est une machine de Turing.
D´ efinition 13.2 Une machine de Turing standard (M) est un triplet
M = (Q, X, ϕ)
o` u Q est un ensemble fini appel´ e alphabet d’´ etat, X est un ensemble fini appel´ e alphabet
de ruban et ϕ : D → Q × X × {−1, 0, 1} est une fonction de domaine D ⊂ Q × X et
o` u −1, 0, 1 repr´ esentent les options du pointeur : respectivement aller ` a gauche, rester
en place et aller `
a droite. Notons que Q et X sont en g´ en´ eral des alphabets disjoints,
c’est-` a-dire Q ∩ X = ∅. De plus, q 0 ∈ Q est nomm´ e l’´ etat initial, B ∈ X est le symbole
blanc et le sous-ensemble Q f ⊂ Q est l’ensemble final d’´ etats.
Fin de l’exemple 13.1 Dans cette notation, la machine de Turing de l’exemple 13.1
est d´ efinie par Q = {q 0 , q 1 , q 2 }, X = {1, 0, B}, Q f = {q 2 } et la fonction ϕ de la table
13.1 : le symbole de d´ epart (l’entr´ ee), qui est un ´ el´ ement de X, se trouve dans la colonne
de gauche, et l’´ etat de d´ epart (un ´ el´ ement de Q) se trouve dans la rang´ ee du haut. On lit
dans la case correspondante du tableau le symbole de sortie, le nouvel ´ etat et la constante
c indiquant le d´ eplacement associ´ es ` a la fonction ϕ.
q0
q1
q2
B (q1, B, 1) (q2, B, −1)
0
(q1, 1, 1)
(q2, 0, −1)
1
(q1, 0, 1)
(q2, 1, −1)
Tab. 13.1. La fonction ϕ de l’exemple 13.1
Remarque Le ruban d’une machine de Turing standard est non born´ e dans une direction. Il existe cependant des machines de Turing dont le ruban est non born´ e ` a droite
et ` a gauche ainsi que des machines ` a plusieurs rubans. Il est possible de prouver que ces
13 L’ordinateur ` a ADN
Bq 2 01100B
q 2 B01100B
Nous avons atteint la position finale. En effet, aucun mouvement n’est pr´ evu lorsque
la machine est dans l’´ etat q 2 et pointe vers un B. Donc, elle est forc´ ee de s’arrˆ eter, et
nous avons le r´ esultat escompt´ e.
Nous voyons ` a pr´ esent l’utilit´ e des diff´ erents ´ etats : pour un mˆ eme symbole, l’op´ eration effectu´ ee par la machine et la direction dans laquelle elle se d´ eplace d´ ependent de
l’´ etat dans lequel elle se trouve. On voit aussi pourquoi il ne faut pas changer d’´ etat si
on r´ ep` ete toujours la mˆ eme op´ eration. Cela permet `
a la machine, qui a un nombre fini
d’instructions de traiter un nombre arbitrairement grand d’entr´ ees 0 et 1 entre les deux
symboles B.
Nous pouvons maintenant d´ efinir plus rigoureusement ce qu’est une machine de Turing.
D´ efinition 13.2 Une machine de Turing standard (M) est un triplet
M = (Q, X, ϕ)
o` u Q est un ensemble fini appel´ e alphabet d’´ etat, X est un ensemble fini appel´ e alphabet
de ruban et ϕ : D → Q × X × {−1, 0, 1} est une fonction de domaine D ⊂ Q × X et
o` u −1, 0, 1 repr´ esentent les options du pointeur : respectivement aller ` a gauche, rester
en place et aller `
a droite. Notons que Q et X sont en g´ en´ eral des alphabets disjoints,
c’est-` a-dire Q ∩ X = ∅. De plus, q 0 ∈ Q est nomm´ e l’´ etat initial, B ∈ X est le symbole
blanc et le sous-ensemble Q f ⊂ Q est l’ensemble final d’´ etats.
Fin de l’exemple 13.1 Dans cette notation, la machine de Turing de l’exemple 13.1
est d´ efinie par Q = {q 0 , q 1 , q 2 }, X = {1, 0, B}, Q f = {q 2 } et la fonction ϕ de la table
13.1 : le symbole de d´ epart (l’entr´ ee), qui est un ´ el´ ement de X, se trouve dans la colonne
de gauche, et l’´ etat de d´ epart (un ´ el´ ement de Q) se trouve dans la rang´ ee du haut. On lit
dans la case correspondante du tableau le symbole de sortie, le nouvel ´ etat et la constante
c indiquant le d´ eplacement associ´ es ` a la fonction ϕ.
q0
q1
q2
B (q1, B, 1) (q2, B, −1)
0
(q1, 1, 1)
(q2, 0, −1)
1
(q1, 0, 1)
(q2, 1, −1)
Tab. 13.1. La fonction ϕ de l’exemple 13.1
Remarque Le ruban d’une machine de Turing standard est non born´ e dans une direction. Il existe cependant des machines de Turing dont le ruban est non born´ e ` a droite
et ` a gauche ainsi que des machines ` a plusieurs rubans. Il est possible de prouver que ces