modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire De Wikipédia, l'encyclopédie libre
Pour les articles homonymes, voir Turing.
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
À l'origine, le concept de machine de Turing, inventé avant l'ordinateur, était censé représenter une personne virtuelle exécutant une procédure bien définie, en changeant le contenu des cases d'un ruban infini, en choisissant ce contenu parmi un ensemble fini de symboles. D'autre part, à chaque étape de la procédure, la personne doit se placer dans un état particulier parmi un ensemble fini d'états. La procédure est formulée en termes d'étapes élémentaires du type : « si vous êtes dans l'état 42 et que le symbole contenu sur la case que vous regardez est « 0 », alors remplacer ce symbole par un « 1 », passer dans l'état 17, et regarder maintenant la case adjacente à droite ».
La thèse de Church postule que tout problème de calcul fondé sur une procédure algorithmique peut être résolu par une machine de Turing. Cette thèse n'est pas un énoncé mathématique, puisqu'elle ne suppose pas une définition précise des procédures algorithmiques. En revanche, il est possible de définir une notion de « système acceptable de programmation » et de démontrer que le pouvoir de tels systèmes est équivalent à celui des machines de Turing (ils sont Turing-complets).
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 :
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 où :
Il s'agit d'un modèle de machine de Turing complète et déterministe ; i.e est définie et unique[3].
Les flèches dans la définition de 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 : signifie que si la machine de Turing est dans l'état et qu'elle lit le symbole , alors elle écrit à la place de , va dans l'état , 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 , 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 dans la définition. On peut ainsi travailler plus précisément sur cet alphabet en réservant certains symboles de l'alphabet complet pour les étapes de calcul de la machine. En particulier, le symbole blanc 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.
La machine de Turing qui suit possède un alphabet {‘0’, ‘1’}, ‘0’ étant le « symbole blanc ». On suppose que le ruban contient une série de ‘1’, et que la tête de lecture/écriture se trouve initialement au-dessus du ‘1’ le plus à gauche. Cette machine a pour effet de doubler le nombre de ‘1’, en intercalant un ‘0’ entre les deux séries. Par exemple, « 111 » devient « 1110111 ».
L’ensemble d’états possibles de la machine est {e1, e2, e3, e4, e5} et l’état initial est e1.
La table d’actions est la suivante :
| Ancien état | Symbole lu | Symbole écrit | Mouvement | Nouvel état |
|---|---|---|---|---|
| e1 | 0 | (Arrêt) | ||
| 1 | 0 | Droite | e2 | |
| e2 | 1 | 1 | Droite | e2 |
| 0 | 0 | Droite | e3 | |
| e3 | 1 | 1 | Droite | e3 |
| 0 | 1 | Gauche | e4 | |
| e4 | 1 | 1 | Gauche | e4 |
| 0 | 0 | Gauche | e5 | |
| e5 | 1 | 1 | Gauche | e5 |
| 0 | 1 | Droite | e1 | |
L’exécution de cette machine pour une série de deux '1' serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et rouges) :
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Le comportement de cette machine peut être décrit comme une boucle :
Ce processus se répète jusqu’à ce que e1 tombe sur un 0 (c’est le 0 du milieu entre les deux séquences de 1) ; à ce moment, la machine s’arrête.
Dans l'exemple qui suit, la machine de Turing possède un ruban vide et permet de construire la suite 01010101010101...
| Ancien état | Symbole écrit | Mouvement | Nouvel état |
|---|---|---|---|
| a | 0 | Droite | b |
| b | 1 | Droite | a |
L’exécution de cette machine serait (la position de la tête de lecture/écriture sur le ruban est inscrite en caractères gras et magenta) :
| Étape | État | Ruban |
|---|---|---|
| 1 | a | 0 |
| 2 | b | 01 |
| 3 | a | 010 |
| 4 | b | 0101 |
| 5 | a | 01010 |
| 6 | b | 010101 |
| 7 | a | 0101010 |
| 8 | b | 01010101 |
| ... | ... | 01010101... |
Le comportement de cette machine peut être décrit comme une boucle infinie :
Cette machine est la contrepartie du calcul de un tiers dont l'écriture en binaire est 0,010101010101...; en effet dans le système binaire et
soit un tiers écrit dans le système binaire.
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.
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.
Seamless Wikipedia browsing. On steroids.
