machine de Turing

Imaginez un ruban quadrillé, un crayon capable de lire ou d'effacer un signe, et une petite liste d'instructions. À chaque étape, la machine regarde une seule case. Selon le signe lu et son état interne, elle change d'état et accomplit une action : elle écrit un symbole ou se déplace d'une case.

Le ruban est supposé infini pour ne pas imposer de limite de mémoire au modèle. Avec ce matériel volontairement minimal, une suite d'actions mécaniques devient un objet mathématique que l'on peut décrire et suivre sans ambiguïté.

Une machine de Turing est un modèle abstrait de calcul. Dans la convention de la définition source, elle est donnée par cinq éléments : un ensemble fini Q d'états internes, un alphabet fini A, un état initial p appartenant à Q, un symbole blanc b qui n'appartient pas à A, et une fonction de transition d. L'alphabet B du ruban réunit les symboles de A et le blanc : $B:=A\cup \{b\}B\; :=\; A\; \backslash cup\; \backslash \{b\backslash \}$.

Le ruban comporte une infinité de cases, chacune portant un symbole de B. Une tête lit une case à la fois. La fonction de transition partielle d reçoit l'état courant et le symbole lu, puis, lorsqu'elle est définie, fournit une action et l'état suivant : Dans cette écriture, l'action est soit un symbole de B à inscrire sur la case courante, soit une flèche indiquant un déplacement d'une case. Chaque application de d détermine donc exactement l'étape suivante selon cette convention ; la machine s'arrête lorsque d n'est pas définie pour l'état courant et le symbole lu.

La machine formalise ainsi un procédé mécanique comme une succession de configurations. Ce modèle suffit, en théorie, à simuler tout calcul algorithmique au sens de la thèse de Church-Turing. Cette thèse est un postulat sur la notion de calcul effectif ; elle ne transforme pas le ruban infini en objet matériel.

On rencontre la machine de Turing dans une description théorique de calcul plutôt que sur un établi. Quatre marqueurs permettent de la reconnaître : un ruban divisé en cases, un alphabet fini de symboles, une tête placée sur une seule case et un nombre fini d'états internes. Une règle de transition associe enfin une action à chaque couple formé par l'état courant et le symbole lu.

Ce support encode à la fois les données du calcul sur le ruban et son avancement dans la position de la tête et l'état interne. Il sert en informatique théorique et en logique mathématique à formuler ce qu'un algorithme peut effectuer mécaniquement.

La donnée à lire est une configuration : le contenu utile du ruban, la case visée par la tête et l'état interne courant. Pour suivre une exécution, procédez dans cet ordre.
1. Relevez l'état courant et le symbole de la case lue.
2. Cherchez ce couple dans la fonction de transition.
3. Exécutez l'action indiquée : écrire un symbole ou déplacer la tête d'une case.
4. Remplacez l'état courant par l'état suivant, puis recommencez.

La convention de la source sépare l'écriture et le déplacement : une transition accomplit l'une de ces actions. L'œil peut croire que seul le ruban compte, mais deux rubans identiques peuvent conduire à des suites différentes si la tête ou l'état diffère. Le bon réflexe consiste à noter les trois composantes à chaque étape.

Suivons une machine sur trois cases visibles, le reste du ruban étant blanc. L'alphabet A contient 0 et 1 ; le symbole blanc est b. Les états utilisés sont q₀, q₁, q₂ et q₃. Au départ, la tête vise la première case, qui contient 1, et l'état est q₀. Les deux cases suivantes contiennent b.

La fonction de transition d fournit les trois règles nécessaires :

1. La première règle remplace 1 par 0. La tête reste sur la première case et l'état devient q₁.

2. La deuxième règle déplace la tête d'une case vers la droite. Le ruban ne change pas et l'état devient q₂.
3. La tête lit alors b. La troisième règle écrit 1 sur cette deuxième case et place la machine dans l'état q₃.

Après exactement trois transitions, les trois cases visibles contiennent donc 0, 1 et b ; la tête vise la deuxième case. Le contrôle consiste à relire les règles dans l'ordre : une écriture, un déplacement, puis une écriture. La figure conserve séparément le ruban, la tête et l'état dans chaque configuration.

Pour analyser un algorithme, on peut traduire chaque instruction élémentaire en transition et suivre les configurations obtenues. Une description ordinaire reste préférable pour exécuter rapidement une tâche ; la machine de Turing devient utile lorsque la question porte sur ce qu'un procédé mécanique peut calculer.

En informatique théorique, le ruban et la fonction de transition rendent chaque étape vérifiable. Un autre modèle de calcul peut être plus commode pour concevoir un programme, tandis que la machine de Turing offre un cadre volontairement minimal pour raisonner sur les algorithmes.

En histoire des idées, ce modèle éclaire la formalisation du calcul par Alan Turing dans les années 1930. Pour étudier les machines électromécaniques auxquelles il contribua vers 1944, il faut toutefois considérer leurs dispositifs concrets plutôt que les identifier au ruban théorique.

Un ordinateur matériel. Une machine de Turing possède par définition un ruban de longueur infinie, alors qu'une machine construite dispose de ressources finies. Si la question porte sur la mémoire disponible ou la vitesse réelle, il faut étudier l'ordinateur concret.

La thèse de Church-Turing. La machine est un modèle formel dont les transitions se suivent pas à pas. La thèse est le postulat selon lequel tout calcul algorithmique peut être réalisé par ce modèle. Une table de transitions décrit donc une machine ; elle ne démontre pas à elle seule la thèse.

Les machines de déchiffrement de la Seconde Guerre mondiale. Elles étaient électromécaniques et concrètes. Le ruban infini signale immédiatement le modèle théorique, même si Alan Turing a aussi contribué à des réalisations de déchiffrement vers 1944.

Ruban infini. Cette longueur est une idéalisation qui retire une borne de mémoire fixée à l'avance. Dès qu'une capacité finie intervient, il faut l'intégrer au modèle étudié au lieu de prêter cette contrainte à la machine de Turing abstraite.

Une configuration ne se réduit pas au ruban. Dans l'exemple, après la première puis après la deuxième transition, le ruban contient dans les deux cas 0, b, b. Pourtant, la tête et l'état ont changé. Il faut donc conserver ruban, position et état ensemble.

Convention de transition. Dans le quintuplet donné ici, une action écrit un symbole ou déplace la tête. Si une autre présentation regroupe plusieurs gestes dans une transition, il faut suivre sa définition propre avant de comparer deux décomptes d'étapes.

Portée de la thèse. La thèse de Church-Turing porte sur ce qui est calculable par un procédé algorithmique. Elle n'affirme ni qu'un calcul se termine vite, ni qu'une machine physique possède des ressources infinies. Il faut séparer possibilité théorique et réalisation pratique.

algorithme — Pour relier la suite d'instructions au calcul effectif que la machine formalise.

automate — Pour situer la machine de Turing parmi les modèles décrits par des états et des transitions.

La vie d'Alan Turing en BD — Pour replacer le modèle dans le parcours intellectuel et historique de son auteur.