Machines de Turing : Définition et Simulation

Bonjour,

Dans la leçon précédente, nous avons franchi une étape décisive en construisant un automate à pile pour reconnaître le langage $L = {a^{n} b^{n} ∣ n \geq 0}$ . Nous avons vu que la pile, avec sa discipline LIFO (dernier entré, premier sorti), est l'outil parfait pour gérer la correspondance symétrique des 'a' et des 'b'. Cependant, ce modèle a ses limites. Que se passerait-il si nous voulions reconnaître le langage $L^{'} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ ? L'automate à pile, après avoir dépilé les 'a' pour les comparer aux 'b', aurait "oublié" leur nombre initial et ne pourrait plus effectuer la vérification avec les 'c'.

Pour surmonter cette limitation, nous devons introduire un modèle de calcul plus puissant. C'est l'objet de notre leçon : la machine de Turing. Conçue par Alan Turing en 1936, cette machine n'est pas seulement un autre type d'automate ; elle est le fondement théorique de ce que nous appelons aujourd'hui un "ordinateur". Elle est si puissante qu'on postule (via la thèse de Church-Turing) que tout ce qui est "calculable" par un algorithme peut l'être par une machine de Turing.

L'objectif d'aujourd'hui est double et fondamental pour l'agrégation : définir formellement une machine de Turing et apprendre à simuler son exécution. Nous allons décortiquer son mécanisme, comprendre sa définition rigoureuse et suivre pas à pas son fonctionnement sur un exemple.

1. Le modèle conceptuel de la machine de Turing

Avant de plonger dans le formalisme, il est crucial de se construire une image mentale claire du fonctionnement d'une machine de Turing. Elle est conceptuellement simple, mais ses implications sont immenses.

Les différences clés avec un automate à pile sont :

La mémoire : Au lieu d'une pile, la mémoire est un ruban infini divisé en cases.
La tête de lecture/écriture : Une unique tête peut non seulement lire le symbole dans une case, mais aussi l'écrire (le modifier) et se déplacer d'une case vers la gauche ou vers la droite.
L'entrée : Le mot d'entrée est initialement écrit sur le ruban. Le reste du ruban est rempli d'un symbole spécial "blanc".

Cette capacité à lire, écrire et se déplacer librement sur le ruban confère à la machine de Turing une puissance de calcul bien supérieure.

Pour une introduction visuelle et intuitive à ces concepts, la vidéo suivante est un excellent point de départ.

Turing Machines - what are they? + Formal Definition

Cette vidéo de Easy Theory (en anglais, mais les concepts sont universels) explique pourquoi un modèle plus puissant que les automates à pile est nécessaire et présente les composants de base d'une machine de Turing.

Regardez les deux premières sections de la vidéo (00:00 à 09:03). Concentrez-vous sur : La motivation : pourquoi les langages comme aⁿbⁿcⁿ nécessitent un nouveau modèle (jusqu'à 02:32). La description du ruban, de la tête de lecture/écriture, et des opérations possibles (lire, écrire, se déplacer à gauche/droite) (de 02:32 à 09:03). Notez en particulier la gestion du ruban infini et des bords.

2. Définition formelle d'une machine de Turing

L'intuition est nécessaire, mais l'agrégation exige une rigueur absolue. Vous devez être capable de définir une machine de Turing avec la précision d'un mathématicien. Pour cela, nous allons nous appuyer sur une ressource académique de référence.

[PDF] Modèles de calculs

Le document PDF suivant, issu d'un cours de l'École Polytechnique, présente la définition formelle d'une machine de Turing telle qu'elle est classiquement enseignée dans le supérieur en France. C'est le type de formalisme que vous devez maîtriser.

Lisez la section 7.1.2 'Description' (page 3). Portez une attention particulière à la Définition 7.1 qui décrit la machine de Turing comme un 8-uplet. Identifiez chacun des composants et son rôle.

Synthétisons et détaillons la définition vue dans le document. Une machine de Turing (MT) est un 8-uplet $M = (Q, Σ, Γ, B, δ, q_{0}, q_{a}, q_{r})$ où :

$Q$ est un ensemble fini d'états.
$Σ$ est l'alphabet d'entrée, qui ne contient pas le symbole blanc.
$Γ$ est l'alphabet de travail (ou alphabet de ruban). Il contient l'alphabet d'entrée ( $Σ \subset Γ$ ) et le symbole blanc.
$B \in Γ ∖ Σ$ est le symbole blanc (ou blank). Il remplit le ruban à l'infini au-delà du mot d'entrée.
$q_{0} \in Q$ est l'état initial.
$q_{a} \in Q$ est l'unique état d'acceptation.
$q_{r} \in Q$ est l'unique état de refus. Dès que la machine entre dans $q_{a}$ ou $q_{r}$ , elle s'arrête (on dit qu'elle halte).
$δ$ est la fonction de transition. C'est le "programme" de la machine. Sa signature est :
$δ : (Q ∖ {q_{a}, q_{r}}) \times Γ \to Q \times Γ \times {\leftarrow, \to, ∣}$
Cela signifie que pour un état courant (qui n'est ni acceptant ni refusant) et un symbole lu sur le ruban, la fonction spécifie :
- Le nouvel état dans lequel passer.
- Le nouveau symbole à écrire dans la case courante.
- Le déplacement de la tête : ← (gauche), → (droite), ou | (ne pas bouger).

Remarque terminologique : Vous rencontrerez d'autres notations. Le déplacement peut être noté L, R, S (Left, Right, Stay) ou -1, +1, 0. Le symbole blanc est souvent noté $□$ . L'important est de comprendre que ces formalismes sont équivalents.

3. Simulation de l'exécution

"Exécuter" une machine de Turing revient à suivre la séquence de ses configurations. C'est l'essence de la simulation.

La configuration

Pour décrire l'état complet de la machine à un instant t, il ne suffit pas de connaître son état interne. Il faut aussi connaître le contenu de son ruban et la position de la tête. C'est ce qu'on appelle une configuration.

Une notation très pratique, présentée dans la ressource LINK, représente une configuration par le triplet (q, u, v) où :

q est l'état courant.
u est la partie du ruban à gauche de la tête, lue de droite à gauche.
v est la partie du ruban à partir de la tête vers la droite, lue de gauche à droite.

Une autre notation, équivalente et plus visuelle, est uqv, où la position de l'état q indique la position de la tête sur le ruban.
Par exemple, si le ruban contient ...B0110B..., que la machine est dans l'état q_2 et que la tête pointe sur le second 1, la configuration peut se noter 0q_210.

La relation de transition `⊢`

On note $C ⊢ C^{'}$ pour signifier que la machine passe de la configuration $C$ à la configuration $C^{'}$ en une seule étape d'exécution (en appliquant une règle de $δ$ ). Un calcul est une séquence de configurations $C_{0} ⊢ C_{1} ⊢ C_{2} ⊢ \dots$ .

Langage accepté, refusé, et boucle

Soit un mot d'entrée w. La configuration initiale est $C_{0} = (q_{0}, ϵ, w)$ (ou $q_{0} w$ ).

Le mot w est accepté s'il existe un calcul fini $C_{0} ⊢ \dots ⊢ C_{n}$ où $C_{n}$ est une configuration acceptante (c'est-à-dire dont l'état est $q_{a}$ ).
Le mot w est refusé s'il existe un calcul fini où la configuration finale est refusante (état $q_{r}$ ).
La machine boucle sur w si le calcul n'est ni acceptant ni refusant (il ne s'arrête jamais).

4. Exemple de simulation : le langage ${0^{n} 1^{n}}$

Mettons tout cela en pratique. Même si ce langage est hors-contexte, il est très instructif de voir comment une MT le traite. Nous allons analyser une machine complète pour ce langage.

[PDF] Modèles de calculs

Retournons au document de Polytechnique. La section suivante décrit en détail une machine de Turing pour {0^n1^n}, sa représentation graphique, et une trace d'exécution complète. C'est un exemple parfait pour maîtriser la simulation.

Étudiez attentivement les sections 7.1.3 'Programmer avec des machines de Turing' et les exemples qui suivent (pages 6 à 9). Analysez la stratégie de l'algorithme : marquer un 0 (le transformer en X), chercher un 1 correspondant, le marquer (en Y), puis revenir au début. Examinez le diagramme d'états : c'est la représentation la plus intuitive de la fonction δ. Chaque arc a/a' m correspond à une transition δ(q, a) = (q', a', m). Suivez l'Exemple 7.5, qui est la trace du calcul sur 0011. Reproduisez les premières étapes sur papier pour vous assurer de bien comprendre la relation ⊢. Enfin, regardez l'Exemple 7.6 (Diagramme espace-temps). C'est une visualisation puissante de l'évolution du ruban au fil du temps.

La simulation est une compétence mécanique, mais qui demande de la rigueur. Chaque étape doit être justifiée par une règle de transition. Le diagramme d'états est votre meilleur ami pour visualiser le "programme".

Simulateur de Machine de Turing — Cette image montre l'interface d'un simulateur de machine de Turing. On y voit la description formelle (règles de transition), le diagramme d'états, le ruban et la tête de lecture, et l'historique du calcul. Cela illustre comment les concepts formels que nous étudions sont mis en œuvre dans des outils pratiques.

Conclusion

Aujourd'hui, nous avons fait un saut conceptuel majeur, passant des automates à mémoire limitée à un modèle de calcul universel.

Les points essentiels à retenir :

La machine de Turing étend les automates finis avec un ruban infini et une tête de lecture/écriture mobile, lui conférant une puissance de calcul bien supérieure.
Sa définition formelle est un 8-uplet $(Q, Σ, Γ, B, δ, q_{0}, q_{a}, q_{r})$ qui capture tous les aspects de son fonctionnement. La maîtrise de cette définition est non négociable.
L'exécution d'une MT est une séquence de configurations, chacune décrivant l'état interne, le contenu du ruban et la position de la tête.
Simuler une MT, c'est dérouler cette séquence de configurations en appliquant la fonction de transition $δ$ à chaque étape, via la relation $⊢$ .

Vous avez maintenant les outils pour comprendre comment une machine de Turing fonctionne. Dans notre prochaine leçon, nous passerons de la simulation à la conception. L'objectif sera de construire une machine de Turing pour un langage que les automates à pile ne peuvent pas reconnaître : le fameux ${a^{n} b^{n} c^{n} ∣ n \geq 0}$ . Cette construction mettra à l'épreuve votre compréhension du modèle et votre capacité à penser "algorithmiquement" sur un ruban.

Recommended resources