13.3 Machines de Turing et fonctions r´ ecursives
423
se trouver la machine de Turing, alors que les fl` eches d´ ecrivent les actions qu’elle peut
accomplir. La fl` eche entrant dans le cercle q 0 indique que cet ´ etat est l’´ etat initial. Le
double cercle autour de q 2 indique que q 2 est l’´ etat final. Une fl` eche partant du cercle q i ,
se rendant au cercle q j et surmont´ ee par une chaˆ ıne de type « x k /x l c » o` u c ∈ {−1, 0, 1}
est interpr´ et´ ee ainsi : si la machine pointe vers une case contenant le symbole x k alors
qu’elle est dans l’´ etat q i , elle remplace le symbole x k par x l , passe ` a l’´ etat q j et se d´ eplace
de c cases, c’est-` a-dire que si c = −1, elle se d´ eplace d’une case vers la gauche ; si c = 0,
elle reste en place ; si c = 1, elle se d´ eplace d’une case vers la droite.
Suivons les ´ etapes effectu´ ees par la machine sur le ruban initial B10011B par
exemple. Au d´ epart, le pointeur est dans l’´ etat q 0 et pointe vers le premier B. Nous allons repr´ esenter cette configuration de la machine par la chaˆ ıne de caract` eres ci-dessous.
Notons que nous ´ ecrivons l’´ etat du pointeur ` a gauche du symbole qu’il rep` ere. Ainsi,
q 0 B10011B
signifie que la machine est dans l’´ etat q 0 , que le pointeur est situ´ e sur la case correspondant au B le plus `
a gauche et que le ruban est dans la configuration B10011B. La
machine passe `
a l’´ etat q 1 , et le pointeur se d´ eplace d’une case vers la droite. Le pointeur
change alors les 1 qu’il rencontre en 0 et les 0 en 1 tout en se d´ epla¸ cant chaque fois
d’une case vers la droite, jusqu’` a ce qu’il rencontre le symbole B. Comme la machine
fait toujours la mˆ eme chose lorsqu’elle rencontre un 0 ou un 1, elle n’a pas besoin de
changer d’´ etat entre deux actions. Ceci donne la suite de configurations
Bq 1 10011B
B0q 1 0011B
B01q 1 011B
B011q 1 11B
B0110q 1 1B
B01100q 1 B
Lorsque nous rencontrons le second symbole B, nous savons que tous les 0 ont ´ et´ e
chang´ es en 1 et vice versa. Reste `
a ramener le pointeur sur la premi` ere case. Pour
cela, la machine passe `
a l’´ etat q 2 , et le pointeur se d´ eplace vers la gauche, une case `
a la
fois, jusqu’` a ce qu’il lise le symbole B.
B0110q 2 0B
B011q 2 00B
B01q 2 100B
B0q 2 1100B
423
se trouver la machine de Turing, alors que les fl` eches d´ ecrivent les actions qu’elle peut
accomplir. La fl` eche entrant dans le cercle q 0 indique que cet ´ etat est l’´ etat initial. Le
double cercle autour de q 2 indique que q 2 est l’´ etat final. Une fl` eche partant du cercle q i ,
se rendant au cercle q j et surmont´ ee par une chaˆ ıne de type « x k /x l c » o` u c ∈ {−1, 0, 1}
est interpr´ et´ ee ainsi : si la machine pointe vers une case contenant le symbole x k alors
qu’elle est dans l’´ etat q i , elle remplace le symbole x k par x l , passe ` a l’´ etat q j et se d´ eplace
de c cases, c’est-` a-dire que si c = −1, elle se d´ eplace d’une case vers la gauche ; si c = 0,
elle reste en place ; si c = 1, elle se d´ eplace d’une case vers la droite.
Suivons les ´ etapes effectu´ ees par la machine sur le ruban initial B10011B par
exemple. Au d´ epart, le pointeur est dans l’´ etat q 0 et pointe vers le premier B. Nous allons repr´ esenter cette configuration de la machine par la chaˆ ıne de caract` eres ci-dessous.
Notons que nous ´ ecrivons l’´ etat du pointeur ` a gauche du symbole qu’il rep` ere. Ainsi,
q 0 B10011B
signifie que la machine est dans l’´ etat q 0 , que le pointeur est situ´ e sur la case correspondant au B le plus `
a gauche et que le ruban est dans la configuration B10011B. La
machine passe `
a l’´ etat q 1 , et le pointeur se d´ eplace d’une case vers la droite. Le pointeur
change alors les 1 qu’il rencontre en 0 et les 0 en 1 tout en se d´ epla¸ cant chaque fois
d’une case vers la droite, jusqu’` a ce qu’il rencontre le symbole B. Comme la machine
fait toujours la mˆ eme chose lorsqu’elle rencontre un 0 ou un 1, elle n’a pas besoin de
changer d’´ etat entre deux actions. Ceci donne la suite de configurations
Bq 1 10011B
B0q 1 0011B
B01q 1 011B
B011q 1 11B
B0110q 1 1B
B01100q 1 B
Lorsque nous rencontrons le second symbole B, nous savons que tous les 0 ont ´ et´ e
chang´ es en 1 et vice versa. Reste `
a ramener le pointeur sur la premi` ere case. Pour
cela, la machine passe `
a l’´ etat q 2 , et le pointeur se d´ eplace vers la gauche, une case `
a la
fois, jusqu’` a ce qu’il lise le symbole B.
B0110q 2 0B
B011q 2 00B
B01q 2 100B
B0q 2 1100B