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: 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

Une machine de Turing est une machine abstraite (qui peut-être vue comme un ordinateur très minimaliste) constituée:
Détaillons le fonctionnement d'une telle machine. 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:

Thèse de Church

Toute fonction «calculable» de façon «intuitive» est calculable au sens ci-dessus par une machine de Turing.
Un peu plus précisément: 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.

Fonctions non-calculables.

Un premier résultat, qui peut paraitre surprenant, énoncé de façon informelle:
La plupart des fonctions de $\mathbb{N}$ dans $\mathbb{N}$ ne sont pas calculables.
Donnons un peu de sens à cela. 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 !
On dispose donc d'une machine de Turing U - dite universelle,
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 tout codé sous forme d'un unique entier en adoptant une convention comme celle de la section précédente)
et qui renvoie 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: Partant de cette machine A, on construit une machine B de façon suivante: La machine B vérifie donc les propriétés suivantes: 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 !

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.