Machine de Turing

Quoique son nom de « machine » puisse conduire à croire le contraire, une machine de Turing est un concept abstrait, c'est-à-dire un objet mathématique. Une machine de Turing comporte les éléments suivants :

1. Un ruban infini divisé en cases consécutives. Chaque case contient un symbole d'un alphabet fini donné. L'alphabet contient un symbole spécial appelé « symbole blanc » ('0' dans les exemples qui suivent), et un ou plusieurs autres symboles. Le ruban est supposé être de longueur illimitée vers la gauche ou vers la droite, en d'autres termes la machine doit toujours avoir assez de longueur de ruban pour son exécution. On considère que les cases du ruban contiennent par défaut le « symbole blanc » ;
2. Une tête de lecture/écriture qui peut lire et écrire les symboles sur le ruban, et se déplacer vers la gauche ou vers la droite du ruban ;
3. Un registre d'état qui mémorise l'état courant de la machine de Turing. Le nombre d'états possibles est toujours fini, et il existe un état spécial appelé « état de départ » qui est l'état initial de la machine avant son exécution ;
4. Une table d'actions qui indique à la machine quel symbole écrire sur le ruban, comment déplacer la tête de lecture (par exemple « ${\displaystyle \leftarrow }$ » pour une case vers la gauche, « ${\displaystyle \rightarrow }$ » pour une case vers la droite), et quel est le nouvel état, en fonction du symbole lu sur le ruban et de l'état courant de la machine. Si aucune action n'existe pour une combinaison donnée d'un symbole lu et d'un état courant, la machine s'arrête.

Plusieurs définitions formelles proches les unes des autres peuvent être données d'une machine de Turing. L'une d'elles[1], relativement courante, est choisie ici. Une machine de Turing est un quintuplet ${\displaystyle (Q,\Gamma ,q_{0},\delta ,F)}$ où :

• ${\displaystyle Q}$ est un ensemble fini d'états ;
• ${\displaystyle \Gamma }$ est l'alphabet de travail des symboles de la bande, contenant ${\displaystyle B}$ un symbole particulier (dit blanc), ${\displaystyle B\in \Gamma }$ ;
• ${\displaystyle q_{0}}$ est l'état initial, ${\displaystyle q_{0}\in Q}$ ;
• ${\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{\leftarrow ,\rightarrow \}}$ est la fonction de transition ;
• ${\displaystyle F}$ est l'ensemble des états acceptants (ou finals[2], terminaux), ${\displaystyle F\subseteq Q}$.

Il s'agit d'un modèle de machine de Turing complète et déterministe ; i.e ${\displaystyle \forall q\in Q,\forall \gamma \in \Gamma ,\delta (q,\gamma )}$ est définie et unique.[3]

Les flèches dans la définition de ${\displaystyle \delta }$ représentent les deux déplacements possibles de la tête de lecture/écriture, à savoir le déplacement à gauche et le déplacement à droite. La signification de cette fonction de transition peut être expliquée sur l'exemple suivant : ${\displaystyle \delta (q_{1},x)=(q_{2},y,\leftarrow )}$ signifie que si la machine de Turing est dans l'état ${\displaystyle q_{1}}$ et qu'elle lit le symbole ${\displaystyle x}$, alors elle écrit ${\displaystyle y}$ à la place de ${\displaystyle x}$, va dans l'état ${\displaystyle q_{2}}$, puis déplace sa tête de lecture vers la gauche.

Le fonctionnement de la machine de Turing est alors le suivant : à chaque étape de son calcul, la machine évolue en fonction de l'état dans lequel elle se trouve et du symbole inscrit dans la case du ruban où se trouve la tête de lecture. Ces deux informations permettent la mise à jour de l'état de la machine grâce à la fonction de transition. À l'instant initial, la machine se trouve dans l'état ${\displaystyle q_{0}}$, et le premier symbole du ruban est l'entrée du programme. La machine s'arrête lorsqu'elle rentre dans un état terminal. Le résultat du calcul est alors le mot formé par les symboles successivement lus par la machine.

On peut contraindre un alphabet des entrées possibles ${\displaystyle \Sigma }$ dans la définition. On peut ainsi travailler plus précisément sur cet alphabet en réservant certains symboles de l'alphabet complet ${\displaystyle \Gamma }$ pour les étapes de calcul de la machine. En particulier, le symbole blanc ${\displaystyle B}$ ne doit pas faire partie de l'entrée et peut donc définir la fin de cette dernière^[pas clair].

Le premier exemple ci-dessous utilise une version très légèrement différente de machine de Turing dans laquelle une machine s'arrête si elle est dans un état terminal et qu'elle lit un certain caractère sur le ruban (ici le symbole blanc). Le deuxième exemple ci-dessous est le premier exemple historique donné par Turing dans son article de 1936 : c'est une machine qui ne s'arrête pas.

Comme Alan Turing le montre dans son article fondateur, il est possible de créer une machine de Turing qu'on appelle « machine de Turing universelle » et qui est capable de « simuler » le comportement de n'importe quelle autre machine de Turing. « Simuler » signifie que si la machine de Turing universelle reçoit en entrée un codage d'une machine T et des données D, elle produit le même résultat que la machine T à laquelle on donnerait en entrée les données D.

Une machine de Turing universelle a la capacité de calculer tout ce qui est calculable : on dit alors qu'elle est Turing-complète. En lui fournissant le codage adéquat, elle peut simuler toute fonction récursive, analyser tout langage récursif, et accepter tout langage partiellement décidable. Selon la thèse de Church-Turing, les problèmes résolubles par une machine de Turing universelle sont exactement les problèmes résolubles par un algorithme ou par une méthode concrète de calcul.

Une machine de Turing est un objet de pensée : son ruban est infini, et donc la mémoire d'une machine de Turing est infinie. Une machine de Turing n'engendre jamais de débordement de mémoire, contrairement à un ordinateur dont la mémoire est finie. En oubliant ce problème de mémoire, on peut simuler une machine de Turing sur un ordinateur moderne.

La machine de Turing en Lego créée à l’occasion de l’année Turing par Elie Gedeon, Etienne Py-Circan, Anael Grandjean, Florent Robic, Robin Perrotin, Thomas Lambert, Yannick Léo, Kevin Perrot et Eddy Caron.

Il est aussi possible de construire des machines de Turing purement mécaniques. La machine de Turing, objet de pensée, a pu ainsi être réifiée à de nombreuses reprises en utilisant des techniques parfois assez originales, dont voici quelques exemples.

• En avril 2011, Jim MacArthur a réalisé une machine de Turing mécanique compacte, à 5 symboles, avec des billes comme support d'informations sur le ruban[4].
• En mars 2012, à l’occasion de l’année Turing (en), une équipe d'étudiants de l'École normale supérieure de Lyon a réalisé une machine de Turing entièrement faite de pièces Lego sans électronique[5]^,[6].

Machine de Turing avec ruban circulaire.

• En décembre 2013, un prototype expérimental pour concrétiser des machines de Turing (électro-mécanique : réalisée avec les technologies de l'époque de Turing) avec un ruban circulaire et relativement facilement programmable. Conçue en deux parties transportables, elle peut être utilisée pour des présentations et des cours[7]^,[8].
• 

  Machine de Turing programmable avec 3 symboles et au plus 12 états.
  En octobre 2020, une machine de Turing pédagogique conçue par Thierry Delattre (Dunkerque), programmable pour des algorithmes ayant au maximum 12 états et avec un alphabet de 3 symboles. 50 algorithmes peuvent être stockés en mémoire. Une version ayant 22 états et 8 symboles date de février 2021[9].