Vous trouverez sur cette page une brève introduction à la machine de Turing et un simulateur qui vous permettra de mettre à l'épreuve votre compréhension du modèle en testant vos propres programmes.
\(\def\baton{Ⅰ}\def\blanc{▣}\def\gauche{🡰}\def\droite{🡲}\)La machine de Turing est un modèle de calcul abstrait introduit en 1936 par le chercheur anglais Alan Turing dans un article fondateur intitulé On Computable Numbers, With An Application To The Entscheidungsproblem dans lequel il propose une réponse à une question posée 8 ans plus tôt par le célèbre mathématicien David Hilbert. Il s'agit du problème de la décidabilité (en allemand Entscheidungsproblem) qui peut être formulé ainsi :
Existe-t-il un algorithme permettant de décider si une proposition formulée dans un système logique est vraie ?
Ce modèle est devenu un outil fondamental en informatique théorique — notamment en théorie de la calculabilité, en théorie de la complexité et en théorie de l'approximation — en raison de sa grande simplicité, qui permet d'établir des résultats rigoureux difficilement accessibles avec des modèles plus complexes.
Comme d'autres, il a été conçu bien avant l'apparition des ordinateurs modernes. Il s'agit donc avant tout d'un outil théorique. Avec la généralisation des ordinateurs dans les années 1950-1960, un autre modèle — le modèle RAM#Register Addressable Memory — a vu le jour, plus proche de l’architecture réelle des machines. Il est remarquable que tous ces modèles soient équivalents du point de vue de ce qu’ils permettent de calculer.
Il est communément admis que tout modèle abstrait de calcul respectant les conditions informelles sur lesquelles les scientifiques s'accordent pour parler d'algorithme — si l'on excepte le calcul quantique qui définit un nouveau paradigme — est équivalent aux précédents. Ce résultat, la thèse de Church-Turing,*Alonzo Church est un mathématicien américain inventeur d'un autre modèle appelé λ-calcul ne peut évidemment pas être démontré puisque le concept d'algorithme est à ce stade un concept informel.
Il convient de garder à l’esprit que la machine de Turing est un modèle de calcul universel, elle est capable de simuler tout processus de calcul réalisable par une machine physique, aussi sophistiquée soit-elle. Inversement, ce qu’elle ne peut calculer ne peut l’être par aucun ordinateur. Elle constitue donc une abstraction puissante du concept d’ordinateur et un cadre idéal pour formaliser les notions d’algorithme, de calcul ou de démonstration.
Il existe de nombreuses formulations de la machine de Turing, motivées par des usages variés, reconnaissance des langages, analyse des problèmes de décidabilité, de calculabilité, de complexité, etc. La versatilité de cet outil théorique explique sa grande popularité. La formulation que nous allons présenter est certainement la plus commune et c'est celle qui est généralement utilisée en théorie de la complexité.
Pour reprendre l'idée même d'Alan Turing, sa machine peut être envisagée comme une version épurée d'une machine à écrire qui ne se limiterait pas à écrire sur la feuille de papier, mais pourrait également en lire le contenu pour décider des actions à réaliser en suivant les instructions d'un programme.
Une machine à écrire opère ponctuellement sur une feuille de papier en y écrivant ou en y effaçant*l'effacement mécanisé avec ruban correcteur ne fut introduit que dans les années 1950, avant on écrivait directement par dessus le caractère erroné. un caractère et en avançant ou en reculant d'une position. La machine de Turing opère quant à elle sur une bande (ou ruban) potentiellement infinie à gauche et à droite et segmentée en cellules (ou cases) pouvant contenir chacune un symbole (cf. figure ci-dessous). Cette bande constitue dans le langage informatique moderne, à la fois le périphérique d'entrée, le périphérique de sortie et la mémoire avec un accès séquentiel#Contrairement au modèle de la machine RAM qui a un accès direct aux cellules de sa mémoire., c'est-à-dire que pour accéder à une cellule donnée de cette mémoire, il faut nécessairement que la machine parcoure toutes les cellules qui la sépare de sa position actuelle. L'indexation des cellules par des entiers relatifs s'avère parfois utile pour certains raisonnements.
Le rôle des barres à caractère de la machine à écrire est joué par la tête de lecture/écriture de la machine de Turing. Elle interagit avec la bande en fonction du contenu de la cellule courante et d'une information interne au programme, son état, qui vont tout deux déterminer la suite du traitement. La tête est matérialisée sur la bande par un cadre rouge autour de la cellule sur laquelle elle est placée, l'état courant du programme est indiqué en-dessous.
Sur cette bande initialement vierge, on inscrit à la main%Virtuellement sur le modèle abstrait, mais réellement sur le simulateur ci-dessus, il suffit de cliquer sur une cellule et d'y saisir un caractère. les données que le programme doit traiter, l'entrée. Ces données sont codées par des mots définis sur un alphabet fini \(\Sigma\) arbitraire. Par convention, on sépare les mots par une cellule vide et le premier symbole du premier mot est placé dans la cellule d'indice \(0\) ou d'indice \(1\), là où se trouve la tête de lecture/écriture initialement.
Pendant l'exécution du programme, la tête de lecture/écriture peut se déplacer à gauche ou se déplacer à droite, lire le contenu de la cellule sur laquelle elle se trouve, l'effacer ou y écrire un symbole en écrasant celui qu'elle contient le cas échéant. À la fin de l'exécution du programme, les symboles sur la bande constituent le résultat du calcul, la sortie.
Ces différentes opérations sont réalisées suivant les règles constituant le programme et qui ne sont que le codage symbolique d'instructions du type :
Ces premiers exemples sont volontairement simples, mais on peut vouloir réaliser des traitements plus fins. Par exemple, effacer la première lettre A rencontrée, mais pas les suivantes, ou encore remplacer uniquement la seconde occurrence d'un symbole. Le symbole contenu dans la cellule courante ne suffit donc pas à déterminer quelle action réaliser. Il faut à la machine une mémoire interne, un moyen de distinguer dans quel contexte elle se trouve lors du traitement. C'est le rôle de son état.
Le fonctionnement du programme de la machine à chaque étape ne dépend donc que de deux paramètres :
Le nombre d'états internes du programme est fixé par le programmeur suivant ses besoins pour réaliser la tâche qu'il veut déléguer à la machine. Parmi ces états, on distingue l'état initial, celui dans lequel se trouve la machine avant le début de l'exécution du programme. Le programme détermine ce que la machine va réaliser en fonction du couple \(({\color{#FF8}p,s})\) constitué par l'état courant de la machine et le symbole lu (si une cellule est vide, on considère qu'elle contient un symbole particulier appelé blanc, que l'on note ici \(\blanc\)).
Un programme est un ensemble de règles (ou instructions ou transitions) de la forme : \begin{equation}\label{eq:rule} ({\color{#FF8}p,s})\mapsto({\color{#88F}e,d,q}). \end{equation}
Le couple \(({\color{#FF8}p,s})\) est appelé condition et le triplet \({\color{#88F}(e,d,q)}\) conséquent. La règle \((\ref{eq:rule})\) est interprétée de la manière suivante :
Si la machine est dans l'état \(\color{yellow}p\) et que le symbole lu est \(\color{yellow}s\), alors elle écrit le symbole \(\color{#88F}e\), se déplace dans la direction \(\color{#88F}d\) et passe dans l'état \(\color{#88F}q\).
avec les interprétations suivantes selon les valeurs de \(e\) et de \(d\) :
On peut à présent décrire le processus d'exécution du programme :
Une modélisation possible de la machine que nous venons de décrire est la suivante :
On intègre parfois dans la définition l'ensemble \(T\subseteq Q\) des états terminaux ou états finaux, c'est-à-dire l'ensemble des états dans lesquels la machine peut se trouver quand elle a terminé son exécution. Ceci peut-être utile pour reconnaître des langages à la manière des automates. Par exemple, dans le cas de problèmes de décision, on définit classiquement \(T:=\{q_Y,q_N\}\), et on dit que \(q_Y\) est l'état d'acceptation et \(q_N\) est l'état de refus.
Il est clair à présent que le programme d'une machine de Turing n'est rien d'autre que le graphe de sa fonction de transition \(\delta\), d'où la définition :
Le contenu d'une bande \(B\) se modélise simplement, il s'agit d'un élément de \(\Gamma^{\Z}\), l'ensemble des applications de \(\Z\) dans \(\Gamma\). Il est donc commode de désigner par \(B[k]\), à la manière des listes où des tableaux, le contenu de la cellule d'indice \(k\). On peut alors définir la configuration d'une machine de Turing, qui est en quelque sorte une photographie instantanée de cette machine :
Compte tenu des conventions et du déroulement des opérations lors de l'exécution du programme, à chaque instant la bande contient un mot de \(\Gamma^*\), elle est donc nécessairement vide de part et d'autre de l'intervalle utile qui borne ce mot, autrement dit \begin{equation*} \exists (g,d)\in{\Z}\times{\Z}\ \ (B[g]\neq\blanc)\wedge(B[d]\neq\blanc)\wedge \big(\forall i\in {\Z}\ (i\not\in\ab{g}{d})\Rightarrow (B[i] = \blanc)\big). \end{equation*}
On peut donc coder le contenu de la bande par le mot de \(u\in \Gamma^*\) qu'elle contient, i.e. la suite des symboles contenu dans les cellules d'indices \(g\) à \(d\), ainsi que sa position \(g\). Il est parfois plus pratique d'exprimer la configuration de la machine par un quadruplet \((q,i,u,g)\) (le couple \((u,g)\in\Gamma^*\times\Z\) n'est qu'un recodage de l'application \(B:\Z\rightarrow\Gamma\)).
Ainsi, avant l'exécution d'un programme et avant que l'utilisateur n'ait saisi le mot d'entrée, la configuration initiale de la machine est donc le triplet \(\chi_0=(q_0,1,\epsilon,1)\) où \(\epsilon\) désigne le mot vide de \(\Gamma^*\). Une fois la bande initialisée avec un mot \(u\in\Gamma^*\), la configuration est \((q_0,1,u,1)\) .
Le diagramme des transitions permet de représenter graphiquement la fonction de transition. Il s'agit d'un multigraphe dont les sommets sont les états de la machine et les arcs représentent les transitions entre deux états. Les arcs sont étiquettés par le symbole en lecture, le symbole en écriture et le nouvel état.
Le rôle des différents boutons qui permettent de contrôler le simulateur est indiqué au survol de ceux-ci. Ils sont suffisamment simples pour limiter les explications qui vont suivre au fonctionnement général du simulateur.
Avant d'utiliser le simulateur, il faut tout d'abord composer votre programme sur votre machine cliente puis il faut le charger dans le simulateur. Un simple éditeur de texte suffit à écrire chacune de ses règles sur une ligne du fichier texte suivant la table de transcodage suivante :
| Modèle | Codage |
| \((p,s)\mapsto(e,d,q)\) | p,s:e,d,s |
| \(\blanc\) | _ |
| 🡰 | < |
| 🡲 | > |
Le simulateur autorise quelques libertés par rapport au modèle abstrait. Chaque terme d'un triplet conséquent \((e,d,q)\) omis dans le fichier programme est interprété respectivement par :
Ainsi, l'instruction q,_:,>, est interprétée comme la boucle tant que la cellule courante est vierge, aller à droite, elle est équivalente à l'instruction q,_:_,>,q. L'instruction q,A:B,,r est équivalente à q,A:B,=,r pour laquelle la tête de lecture/écriture reste fixe après avoir changé le symbole A en B.
Tout ce qui suit le symbole ; est ignoré pour pouvoir insérer des commentaires.
Si la première ligne du fichier commence par ;RUBAN@-4: chaine_de_caracteres, la tête de lecture/écriture est placée sur la cellule d'indice \(-4\) et le contenu de la bande est initialisé avec les symboles de la chaîne de caractère chaine_de_caracteres à partir de cette position. Dans le cas contraire, la bande est vierge et la tête de lecture/écriture est placée sur la cellule d'indice \(0\). L'alphabet de travail est limité à \begin{equation*} \label{eq:gamma} \Gamma:=\texttt{[a-zA-Z0-9!#=*|_]}. \end{equation*}
Par convention, l'état initial est l'état \(p\) de la condition de la première instruction du programme. Les états peuvent être codés par des chaînes constituées de \(1\) à \(4\) caractères dans l'ensemble \(\texttt{[a-zA-Z0-9]}\).
Le diagramme des transitions du programme est tracé dans le simulateur en cliquant sur le bouton ⎌ du bloc de contrôle du programme. Vous pouvez zoomer si nécessaire avec la molette de la souris.
Si \(x\) désigne l'entrée du programme sur la bande, le simulateur calcule d'une part la complexité en temps \(\eta(x)\), c'est-à-dire le nombre de transitions réalisées lors de l'exécution du programme, et d'autre part la complexité en espace \(\epsilon(x)\), i.e. la longueur maximale de l'intervalle utile durant l'exécution du programme.
Tous les programmes fournis ici peuvent être chargés puis exécutés sur le simulateur javascript plus haut.
Quand nous utilisons l'alphabet d'entrée unaire \(\Sigma=\{\baton\}\), l'unique symbole de \(\Sigma\) est appelé bâton. Dans ce cas l'ensemble des entiers naturels \({\N}\) est identifié au langage \(\Sigma^+\) grâce à la bijection \(\varphi:{\N}\rightarrow\Sigma^+\) définie par \(\varphi(n) :=\; \baton^{n+1}\) où la notation exponentielle est associée à la loi de concaténation \(\cdot\) définie sur \(\Gamma^*\). Par exemple \(\baton^3=\; \baton\baton\baton\) et \(\baton^0=\epsilon\) qui désigne usuellement le mot vide.
Entrée : une séquence de \(k\) bâtons sur la bande.
Sortie : une séquence de 2\(k\) bâtons sur la bande.
Le programme opère en effaçant un à un tous les bâtons de la séquence initiale \(u:=\baton^k\) de gauche à droite en rajoutant à chaque effacement, deux bâtons à une séquence \(v\) initialement vide, un à chaque extrémité :
La bande contient initialement \(\baton^k\). On efface le premier bâton de \(u\) à gauche, pour l'écrire à l'extrémité droite de la séquence \(v\) initialement vide et placée à gauche de la séquence \(u\). À ce stade, la bande contient \(\baton\blanc\baton^{k-1}\). On parcourt tous les bâtons de \(v\) vers la gauche (à cette étape \(v\) n'en contient qu'un) et on inscrit le second bâton à l'extrémité gauche de \(v\). La bande contient alors \(\baton\baton\blanc\baton^{k-1}\). On se replace à gauche de la séquence \(u\) qui ne contient plus que \(k-1\) bâtons et on recommence jusqu'à ce que tous les bâtons de \(u\) soient effacés.
Entrée : une séquence de \(k\) bâtons.
Sortie : deux séquences de \(k\) bâtons séparés par une cellule vide.
Toujours avec les même conventions, le programme ci-dessous calcule la fonction \(f:\N\rightarrow\N\times\N\) définie par \(n\mapsto(n,n)\). Il initialise à un bâton une séquence \(v\) à gauche de \(u=\baton^k\) en séparant \(v\) et \(u\) par une cellule vide. Puis on efface un à un les \(n\) premiers bâtons de la séquence \(u\) qui en contient initialement \(n\) + 1. Pour chaque bâton effacé de \(u\), on le rajoute à gauche de \(v\). Une fois qu'il ne reste plus que le dernier bâton à la séquence \(u\), on remplit les \(n\) + 1 cellules vides séparant \(v\) et \(u\), on recrée la cellule séparatrice pour arriver finalement à \(\baton^k\blanc\baton^k\).
Entrée : Une séquence de \(n+1\) bâtons suivie d'une séquence de \(m+1\) bâtons.
Sortie : Une séquence de \(n+m+1\) bâtons.
Le programme ci-dessous calcule la fonction \(f:\N\times\N\rightarrow\N\) définie par \((n,m)\mapsto n+m\). Il suffit de placer un bâton dans la cellule vide qui sépare les deux séquences \(u:=\baton^{n+1}\) et \(v:=\baton^{m+1}\) pour former une uniue séquence de \(n+m+3\) bâtons, puis d'effacer ses deux premiers bâtons.
Entrée : Une séquence de \(n\) + 1 bâtons suivie d'une séquence de \(m\) + 1 bâtons.
Sortie : Une séquence de \(n\times m+1\) bâtons.
Le programme ci-dessous calcule la fonction \(f:\N\times\N\rightarrow\N\) définie par \((n,m)\mapsto n\times m\) avec les conventions usuelles sur l'alphabet unaire. Il procède de la manière suivante : pour chacun des \(n\) premiers bâtons de la première séquence \(u\) qui en contient \(n\) + 1 au départ, recopier les \(m\) premiers bâtons de la seconde séquence \(v\) qui en contient \(m\) + 1 au départ au bout d'une troisième séquence \(w\) initialement vide. Cette copie se fait en effaçant successivement les \(m\) premiers bâtons de \(v\) et en les recopiant au bout de \(w\), le dernier bâton de \(v\) sert à contrôler la fin de la copie après laquelle on reconstitue les \(m\) bâtons effacés pendant la copie. Une fois qu'il ne reste qu'un bâton dans \(u\), la séquence \(w\) en contient \(n\) × \(m\), on peut alors terminer. On efface le dernier bâton de \(u\) ainsi que les \(m\) + 1 bâtons de \(v\) et on rajoute un dernier bâton à la séquence résultat \(w\).
Entrée : un entier \(n\) codé en binaire.
Sortie : Oui/Non.
Cette fois nous utilisons la machine de Turing pour prendre une décision et distinguons deux états particuliers, l'état d'acceptation \(q_Y\) et de l'état de refus \(q_N\) codés par les chaînes O (l'entier est multiple de \(4\)) et N (l'entier n'est pas multiple de 4) dans le programme. On suppose que l'alphabet d'entrée est binaire, i.e. \(\Sigma:=\{0,1\}.\)
On décide facilement si \(n\) est un multiple de \(4\) à l'aide de son écriture binaire. Le cas échéant, soit \(n=0\), et dans ce cas la bande est vide sauf la cellule courante qui contient 0, soit les deux derniers chiffres de \(n\) sont nuls. Le programme est écrit en ce sens. Il commence par déplacer la tête de lecture/écriture sur le bit de poids faible de \(n\), teste sa valeur puis, si nécessaire, teste le contenu de la cellule qui précède pour conclure.
Entrée : un entier \(n\) codé en binaire.
Sortie : l'entier \(2n\).
Le programme se contente de rajouter un \(0\) à la fin de la séquence binaire qui code \(n\) :