Comment fonctionne une machine de Turing ?

Pour ajouter 1 à un nombre binaire, on utilise la table d’addition suivante :

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10 : on pose 0, et on retient 1

Si le nombre binaire en entrée se termine par 0, par exemple :
1001010 + 1 = 1001011
dans ce cas, il suffit de remplacer le dernier 0 par un 1. On parcourt le nombre de gauche à droite, et lorsqu’on arrive à la fin, si on trouve un 0, on le remplace par un 1 et on passe à l’état final.

Si le nombre binaire en entrée se termine par 1, par exemple :
1001011 + 1 = 1001100
dans ce cas, après avoir parcouru le nombre de gauche à droite, on revient de droite à gauche, tant qu’on trouve un 1, on le remplace par un 0, lorsqu’on trouve la première occurrence de 0, on la remplace par 1 puis on passe à l’état final.

Cas particulier de nombre se terminant par 1, un nombre peut être formé seulement par des 1, par exemple :
1111111 + 1 = 10000000
dans ce cas, on remplace tous les 1 par 0 et on insère un 1 dans la première case vide à gauche.

Passons maintenant à la programmation de notre machine.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et lit un 1, elle écrit 1, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 3.

Si elle est à l’état 3 et lit un 1, elle écrit 0, décale le ruban à droite et reste à l’état 3.

Si elle est à l’état 3 et lit un 0, elle écrit 1, décale le ruban à droite et passe à l’état final.

Si elle est à l’état 3 et trouve une case vide, elle écrit 1, décale le ruban à droite et passe à l’état final.

Pour soustraire 1 à un nombre binaire, on utilise la table de soustraction suivante :

0 – 0 = 0
0 – 1 = 1 : on pose 1, et on retient 1
1 – 0 = 1
1 – 1 = 0

Si le nombre binaire en entrée se termine par 1, par exemple :
1001011 – 1 = 1001010
dans ce cas, il suffit de remplacer le dernier 1 par un 0. On parcourt le nombre de gauche à droite, et lorsqu’on arrive à la fin, si on trouve un 1, on le remplace par un 0 et on passe à l’état final.

Si le nombre binaire en entrée se termine par 0, par exemple :
1001010 – 1 = 1001001
dans ce cas, après avoir parcouru le nombre de gauche à droite, on revient de droite à gauche, tant qu’on trouve un 0, on le remplace par un 1, lorsqu’on trouve la première occurrence de 1, on la remplace par 0 puis on passe à l’état final.

Passons maintenant à la programmation de notre machine.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et lit un 1, elle écrit 1, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 3.

Si elle est à l’état 3 et lit un 0, elle écrit 1, décale le ruban à droite et reste à l’état 3.

Si elle est à l’état 3 et lit un 1, elle écrit 0, décale le ruban à droite et passe à l’état final.

Pour la multiplication des nombres binaires, on utilise la table suivante :

1 × 0 = 0
1 × 1 = 1
0 × 0 = 0

En binaire, 2 est noté 10. Cette multiplication revient donc, comme la multiplication par 10 en notation décimale, à ajouter au nombre de départ un 0 à droite, par exemple :
1001010 × 10 = 10010100
on parcourt donc le nombre de gauche à droite, et dès qu’on trouve une case vide à droite, on y insère un 0 et on passe à l’état final.

Passons maintenant à la programmation de notre machine.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et lit un 1, elle écrit 1, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et trouve une case vide, elle écrit 0, décale le ruban à gauche et passe à l’état final.

Il s’agit d’inverser les 0 et les 1 formant un nombre binaire (les 1 deviennent des 0 et les 0 des 1) et de recommencer indéfiniment.

On commence par parcourir le nombre de gauche à droite en remplaçant les 1 par des 0 et les 0 par des 1, puis lorsqu’on rencontre une case vide, on parcourt le nombre dans l’autre sens en remplaçant à nouveau les 0 par des 1 et les 1 par des 0.

Passons maintenant à la programmation de notre machine.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle écrit 1, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et lit un 1, elle écrit 0, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 3.

Si elle est à l’état 3 et lit un 1, elle écrit 0, décale le ruban à droite et reste à l’état 3.

Si elle est à l’état 3 et lit un 0, elle écrit 1, décale le ruban à droite et passe à l’état 3.

Si elle est à l’état 3 et trouve une case vide, elle n’écrit rien, décale le ruban à gauche et passe à l’état 2.

Il s’agit précisément de doubler la longueur d’une suite de 1 inscrits sur le ruban. Pour cela, on parcourt le ruban de gauche à droite, à chaque 1 rencontré, on le remplace par un 0, on retourne vers la gauche et dans la première case vide on ajoute un 0, puis on repart de gauche à droite. Lorsqu’on atteint la première case vide à droite, on parcourt à nouveau le ruban en sens inverse et on remplace tous les 0 par des 1.

Passons maintenant à la programmation de notre machine.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 2.

Si elle est à l’état 2 et lit un 1, elle écrit 0, décale le ruban à droite et passe à l’état 3.

Si elle est à l’état 2 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 4.

Si elle est à l’état 3 et lit un 0, elle écrit 0, décale le ruban à droite et reste à l’état 3.

Si elle est à l’état 3 et trouve une case vide, elle écrit 0, décale le ruban à gauche et passe à l’état 2.

Si elle est à l’état 4 et lit un 0, elle écrit 1, décale le ruban à droite et reste à l’état 4.

Si elle est à l’état 4 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état final.

Un palindrome est un mot qui est identique qu’on le lise de gauche à droite ou de droite à gauche. Par exemple, 101 est un palindrome alors que 100 n’en est pas un.

Le principe d’une Machine de Turing qui teste si un mot binaire écrit sur son ruban est un palindrome est d’itérer les étapes suivantes tant qu’on n’atteint pas l’état OUI ou l’état NON :

on lit le premier symbole de la partie codante du ruban et on l’efface en mémorisant sa valeur (0 ou 1) par un état (e3 ou e6 dans la table d’actions ci-dessous)
on déplace le ruban sans changer d’état jusqu’à atteindre la première case vide.
On passe alors dans l’état e4 (respectivement e7) si on était dans l’état e3 (respectivement e6)
et on recule d’une case pour se positionner sur le dernier symbole de la partie codante du ruban.
si ce symbole est 1 (respectivement 0) alors qu’on est dans l’état e4 mémorisant que le premier symbole était un 0 (respectivement l’état e7 mémorisant que le premier symbole était un 1), on passe dans l’état NON ;
sinon on efface ce dernier symbole et si la partie codante est vide, on passe dans l’état OUI, sinon on déplace le ruban jusqu’à se positionner au début de la partie codante.

La table d’actions utilisée est la suivante :

Voici comment se comporte la machine :

Si elle est à l’état 1 et trouve une case vide, elle n’écrit rien, décale le ruban d’une case à gauche et passe à l’état 2.

Si elle est à l’état 2 et lit un 0, elle efface la case, décale le ruban à gauche et passe à l’état 3.

Si elle est à l’état 2 et lit un 1, elle efface la case, décale le ruban à gauche et passe à l’état 6.

Si elle est à l’état 2 et trouve une case vide, elle n’écrit rien, décale le ruban à gauche et passe à l’état final OUI.

Si elle est à l’état 3 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 3.

Si elle est à l’état 3 et lit un 1, elle écrit 1, décale le ruban à gauche et reste à l’état 3.

Si elle est à l’état 3 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 4.

Si elle est à l’état 4 et lit un 0, elle efface la case, décale le ruban à droite et passe à l’état 5.

Si elle est à l’état 4 et lit un 1, elle écrit 1, décale le ruban à gauche et passe à l’état final NON.

Si elle est à l’état 4 et trouve une case vide, elle n’écrit rien, décale le ruban à gauche et passe à l’état final OUI.

Si elle est à l’état 5 et lit un 0, elle écrit 0, décale le ruban à droite et reste à l’état 5.

Si elle est à l’état 5 et lit un 1, elle écrit 1, décale le ruban à droite et reste à l’état 5.

Si elle est à l’état 5 et trouve une case vide, elle n’écrit rien, décale le ruban à gauche et passe à l’état 2.

Si elle est à l’état 6 et lit un 0, elle écrit 0, décale le ruban à gauche et reste à l’état 6.

Si elle est à l’état 6 et lit un 1, elle écrit 1, décale le ruban à gauche et reste à l’état 6.

Si elle est à l’état 6 et trouve une case vide, elle n’écrit rien, décale le ruban à droite et passe à l’état 7.

Si elle est à l’état 7 et lit un 0, elle écrit 0, décale le ruban à gauche et passe à l’état final NON.

Si elle est à l’état 7 et lit un 1, elle efface la case, décale le ruban à droite et passe à l’état 5.

Si elle est à l’état 7 et trouve une case vide, elle n’écrit rien, décale le ruban à gauche et passe à l’état final OUI.