Page principale

Machines de Turing

Les machines de Turing ont été inventées par Alan Turing en 1936. Ce sont des objets mathématiques permettant de donner un sens précis à la notion de «calcul». Deux théories fondamentales en informatique découlent largement de l'étude des machines de Turing:

• La théorie de la calculabilité: qu'est-il possible de «calculer» ?
• La théorie de la complexité: quel temps cela prend-il ?

Il s'agit sur cette page de présenter ces machines et - de façon largement informelle - des résultats les concernant.

Machine de Turing : définition et exemple

Détaillons le fonctionnement d'une telle machine.

• Les sommets du graphe correspondent à des états possibles de la machine de Turing. Ici, il y en a 3: A, B, et ⊤.
• Le graphe dispose d'un état initial, dans lequel la machine se trouve au départ. Il est indiqué par une flêche entrante, et sur le schéma ci-dessus, c'est A.
• Les arcs du graphes correspondent à des transitions. Par exemple la transition «□1←», qui va de A vers B, signifie que
Si
• la machine est dans l'état A
• qu'elle lit le caractère □ (case vide) sur le ruban (i.e. que la case pointée par la tête de lecture est vide)
Alors
• elle écrit 1 sur le ruban
• elle déplace la tête de lecture d'une case vers la gauche
• elle se place dans l'état B
• Les transitions sont exécutées séquentiellement, jusqu'à ce que
• la machine tente d'exécuter une transition qui n'existe pas - on peut interpréter cela comme une erreur
• la machine arrive dans un état terminal - matérialisé par un double cercle. Ici, il y un unique état terminal: ⊤

Si l'on reprend la machine ci-dessus, initialement dans l'état A et avec le caractère 1 sous la tête de lecture, c'est la transition qui boucle sur A qui va être exécutée. Celle-ci va écrire un 0 sur le ruban, et déplacer la tête de lecture vers la droite. La machine reste dans l'état A, et le ruban est donc maintenant dans l'état suivant:

Essayez de trouver les états successifs de la machine ci-dessus ! Vous pouvez vérifier votre résultat à l'adresse suivante:http://mpechaud.fr/scripts/turingmachine/tm.php?tm=0-A,B,⊤-A-⊤,⊥-□,0,1-A,□,B,1,←_A,0,B,1,←_A,1,A,0,→_B,□,⊤,□,→_B,0,B,0,←_B,1,B,1,←-11011 Ce qui est écrit sur le ruban à la fin de l'exécution (à partir de la tête de lecture) peut être vu comme un résultat - ici 00111.
Avec cette vision des choses, on se convainc facilement, que si les données de départ (i.e. ce qui est écrit sur le ruban) correspondent à l'écriture binaire d'un nombre (bit de poids faible à gauche), le résultat correspond à ce nombre auquel on a ajouté 1.
La machine de Turing ci-dessus correspond donc à la fonction qui à $n\in\mathbb{N}$ associe $n+1$.

À quoi cela sert-il?

Les machines de Turing sont un modèle théorique de calcul. En formalisant un tout petit peu plus la section précédente, on a une définition précise de ce qu'est un calcul sur une machine de Turing, menant de données en entrées (par exemple un entier représenté avec tel ou tel codage) à un résultat. On peut en déduire une définition formelle de fonction calculable - c'est par exemple le cas de $n \mapsto n+1$ comme nous l'avons vu ci-dessus.

Il y a en fait une petite subtilité ici, cette notion semblant dépendre du codage choisi. Ce n'est en fait pas le cas: si l'on dispose d'une machine de Turing permettant de calculer une fonction en codant les entiers de telle ou telle façon, on peut montrer que si l'on modifie ce codage des entiers en un autre codage «raisonnable», on pourra trouver une machine de Turing correspondante.

La notion obtenue est-elle pertinente, autrement dit la notion de fonction «calculable» capture-t-elle bien une certaine intuition de ce que l'on entend par «calculer» (à partir de données et d'une séquence finie d'opérations, parvenir à un résultat) ? Vue la simplicité du modèle des machines de Turing, on pourrait penser que celles-ci ne permettent de faire que des calculs très limités.
La réponse est donnée par la thèse de Church, que l'on peut formuler de la façon informelle suivante: Un peu plus précisément:

• Les fonctions calculables par d'autres modèles de calculs suffisamment riches (machines à registres, machine RAM, λ-calcul...) sont les mêmes que les fonctions calculables par des machines de Turing.
• En particulier toute fonction calculable par un ordinateur l'est par une machine de Turing.

Sous leur apparente simplicité, les machines de Turing sont en fait des modèles universels de calcul.

Pour appréhender un peu naïvement ces possibilités, voici quelques petits problèmes que vous pouvez essayer de résoudre à partir du simulateur.

• Trouver une machine de Turing, qui étant donné un entier $n$ (représenté en binaire avec le bit de poids faible en premier), renvoie $2n$ (i.e. rajoute un 0 au début de l'écriture binaire). Dans le simulateur, l'état terminal est noté ⊤ ou ⊥. La tête de lecture devra être en fin de calcul sur la première lettre du résultat. Solution
• Trouver une machine de Turing, qui étant donnée en entrée une suite de 0 et de 1, renvoie la suite où tous les 0 ont été remplacés par des 1, et réciproquement (en bonus: on replacera en fin de calcul la tête de lecture/écriture au début de cette suite). Solution.
• Trouver une machine de Turing, qui étant donné une suite de 1 contigüs, décide s'il y en a un nombre pair. Cette machine devra donc renvoyer «vrai» ou «faux». Par convention, on code cela selon dans lequel des états terminaux on termine le calcul: ⊤ pour «vrai» et ⊥ pour «faux» (peu importe l'état du ruban ou la position de la tête de lecture à la fin). Solution.
• Plus difficile ! Écrire une machine de Turing qui étant donné un mot constitué de 0 et de 1 en entrée renvoie le miroir de ce mot. Par exemple, le miroir de «101000» est «000101». Solution.
• Écrire une machine de Turing qui renvoie «vrai» (cf ci-dessus) si il y a en entrée un mot de la forme 1...12...23...3 avec le même nombre de 1, de 2 et de 3, et «faux» sinon. Solution.
• Un castor affairé. En utilisant 2 symboles (□ et 1) et 3 états (A,B,C) ainsi que l'état terminal ⊤, écrire une machine de Turing qui, partant du ruban vide, écrit le maximum de «1» sur le ruban avant de s'arrêter. (Indication: on peut arriver jusqu'à 6 «1».) Solution.

Fonctions non-calculables.

Un premier résultat, qui peut paraitre surprenant, énoncé de façon informelle: Donnons un peu de sens à cela.

• L'ensemble des fonctions de $\mathbb{N}$ dans $\mathbb{N}$ est de même cardinalité que $\mathbb{R}$. C'est un petit exercice sur les ensembles. Cela signifie qu'il y a «autant» de fonctions de $\mathbb{N}$ dans $\mathbb{N}$ que de nombres réels.
• L'ensemble des fonctions calculables de $\mathbb{N}$ dans $\mathbb{N}$ est dénombrable. En effet, toute fonction calculable est associée à (au moins) une machine de Turing. Or l'ensemble des machines de Turing est dénombrable: une machine de Turing peut en effet être représentée par une chaine de caractères en prenant des conventions similaires à celles adoptées dans les adresses dirigeant depuis cette page vers le simulateur ! Par exemple, la première machine de Turing présentée est codée par 0-A,B,⊤-A-⊤,⊥-□,0,1-A,□,B,1,←_A,0,B,1,←_A,1,A,0,→_B,□,⊤,□,→_B,0,B,0,←_B,1,B,1,←-, où les caractères qui apparaissent sont «-»,«_»,«,», les flêches, «□», «⊤», «⊥» et des lettres et chiffres. L'ensemble des chaines de caractères finies sur un alphabet fini étant dénombrable, on obtient le résultat. Il y a donc «autant» de fonctions calculables que de nombres entiers! C'est-à-dire beaucoup moins de que de fonctions tout court.

Il y a donc beaucoup de fonctions non-calculables, mais il est difficile d'en construire une explicitement. Intuitivement, lorsque nous pensons à une fonction f, nous pensons à une formule ou à un autre procédé algorithmique qui permet de calculer f(n) en fonction de n, et ce procédé pourra être codé par une machine de Turing !
Nous verrons dans la dernière partie comment obtenir une fonction non-calculable, et pourtant parfaitement définie mathématiquement.

Machine de Turing universelle

Remarquons qu'une machine de Turing peut-être spécifiée par une chaine de caractères, décrivant ses états, l'alphabet du ruban, et les transitions. C'est d'ailleurs ce qui est fait dans cette page pour charger telle ou telle machine de Turing dans le simulateur. Par exemple, la chaine de caractères décrivant la toute première machine décrite ci-dessus est «0-A,B,⊤-A-⊤,⊥-□,0,1-A,□,B,1,←_A,0,B,1,←_A,1,A,0,→_B,□,⊤,□,→_B,0,B,0,←_B,1,B,1,←-». Une telle chaine de caractères peut à son tour être représentée par un entier (prendre par exemple l'entier correspondant en binaire au codage machine de cette chaine, auquel on a ajouté un 1 au début).
Donc à chaque machine de Turing correspond un unique entier, qui la caractérise entièrement.
Étant donné cet entier, on peut le décoder en une chaine de caractères du type de celle donnée ci-dessus, puis simuler la machine de Turing (par exemple en partant d'un ruban vide) - c'est ce que fait le simulateur que vous avez utilisé ci-dessus.
Mais si cette simulation peut-être effectuée par un ordinateur, c'est également qu'elle peut-être effectuée par une certaine machine de Turing U ! Cela se traduit concrètement par un principe très important : le programme (la machine M passée en entrée) peut-être écrit sur la mémoire (i.e. sur un ruban) de la machine universelle. La machine universelle est donc un ordinateur programmable : pour lui faire exécuter tel ou tel algorithme, on place un programme dans sa mémoire, et on n'a pas besoin d'aller toucher au «hardware» (ici aux états et transitions de la machine universelle).

Indécidabilité de l'arrêt

Comme vous vous en êtes peut-être déjà aperçu en utilisant le simulateur, il est possible d'écrire des machines de Turing qui, sur certaines données en entrée, ne terminent jamais. En voici un exemple: http://mpechaud.fr/scripts/turingmachine/tm.php?tm=0-A-A-⊤,⊥-□-A,□,A,□,←-.

On peut se demander s'il existe une machine de Turing A qui prend en argument :

• le numéro d'une machine de Turing M
• un entier k

(le tout codé sous forme d'un unique entier en adoptant une convention comme celle de la section précédente)
et qui renvoie

• 1 si M exécutée à partir de la donnée k finit par s'arrêter
• 0 sinon.

Une telle machine A calcule donc une fonction de $\mathbb{N}$ dans $\mathbb{N}$, qui répond au problème de l'arrêt (i.e. teste si une machine appelée sur une certaine entrée finit par s'arrêter). On va montrer par l'absurde que cette machine de Turing ne peut pas exister, ce qui a 2 conséquences immédiates:

• le problème de l'arrêt est indécidable - il n'existe pas de procédé algorithmique permettant de dire si oui ou non tout procédé algorithmique finira par terminer.
• la fonction de $\mathbb{N}$ dans $\mathbb{N}$ correspondante n'est pas calculable. On aura donc un exemple explicite (quoique compliqué...) de fonction non-calculable.

Partant de cette machine A, on construit une machine B de façon suivante:

• B prend en entrée un entier, correspondant au numéro n d'une machine de Turing
• Elle effectue la même chose que A appelée avec la machine d'entrée n, et la donnée k=n
• si la machine A devait renvoyer 0, on arrête B
• si la machine A devait renvoyer 1, on met B dans un état tel que le calcul ne s'arrête pas (en utilisant un mécanisme similaire à celui de l'exemple ci-dessus).

La machine B vérifie donc les propriétés suivantes:

• elle s'arrête lorsqu'on lui donne en entrée le numéro n d'une machine qui ne s'arrête pas sur la donnée d'entrée n
• elle ne s'arrête lorsqu'on lui donne en entrée le numéro n d'une machine qui s'arrête sur la donnée d'entrée n

Si on lui donne en entrée son propre numéro b, on arrive donc à une contradiction: d'après ce qui précède, B appelée sur la donnée d'entrée b s'arrête si et seulement si B appelée sur la donnée d'entrée b ne s'arrête pas.

Des références pour aller plus loin

Et pour voir raconté de façon propre ce qui précède, et bien d'autres choses !

• Mathématiques de l'informatique, Patrick Dehornoy (Dunod)
• Langages formels, calculabilité et complexité, Olivier Carton (Vuibert)
• Calculabilité, complexité et approximation, Jean-François Rey (Vuibert)

Bestiaire de machines de Turing

N'hésitez pas à m'envoyer (mon_prenom_mon_nom_tout_attaché@protonmail.com) vos réalisations de machines de Turing ! Je les ajouterai à cette page.