Machine de Turing pour Langages Non-Contextuels

1. La stratégie algorithmique : marquer et vérifier

Comment vérifieriez-vous manuellement qu'une chaîne comme aaabbbccc appartient bien à notre langage ? Vous compteriez probablement les symboles. Une machine de Turing fait de même, mais d'une manière très séquentielle. L'approche la plus courante est une stratégie de "marquage" ou de "zigzag" :

1. En partant du début du ruban, on cherche le premier a non marqué. On le lit et on le "marque" en le remplaçant par un symbole spécial, par exemple X.
2. On parcourt ensuite le ruban vers la droite pour trouver le premier b non marqué. On le marque en le remplaçant par un autre symbole, disons Y.
3. On continue vers la droite pour trouver le premier c non marqué. On le marque avec un Z.
4. Une fois ce triplet (a, b, c) marqué, la tête de lecture retourne tout au début du ruban pour recommencer le processus.
5. On répète ces étapes jusqu'à ce qu'il n'y ait plus de a à marquer.
6. À ce stade, si la chaîne était bien formée, tous les a, b, et c devraient être marqués. Il reste une dernière étape de vérification : on parcourt une dernière fois le ruban pour s'assurer qu'aucun b ou c non marqué ne subsiste. Si c'est le cas, la chaîne est acceptée.

La machine doit également gérer les cas d'échec : si à une étape, le symbole attendu n'est pas trouvé (par exemple, on cherche un b mais on tombe sur un c ou le symbole blanc), la chaîne est immédiatement rejetée.

Cette logique peut sembler complexe, mais elle se traduit très naturellement en un diagramme d'états.

2. Construction de la Machine de Turing

Nous allons maintenant formaliser cette stratégie. Chaque étape de l'algorithme correspondra à un ou plusieurs états de notre machine. La vidéo suivante, en français, détaille cette construction de manière très claire.

Synthétisons et formalisons la machine construite dans la vidéo. Soit notre MT $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,B,q_a)$.

• États $Q$: $\{q_0,q_1,q_2,q_3,q_4,q_a\}$. Nous utiliserons des noms d'états qui reflètent leur fonction.
  • $q_0$: État initial. Cherche un a.
  • $q_1$: A marqué un a (X), cherche un b.
  • $q_2$: A marqué un b (Y), cherche un c.
  • $q_3$: A marqué un c (Z), retourne au début.
  • $q_4$: Plus de a, vérifie la fin de la chaîne.
  • $q_a$: État d'acceptation. (L'état de rejet est implicite).
• Alphabet d'entrée $\Sigma$: $\{a,b,c\}$
• Alphabet de ruban $\Gamma$: $\{a,b,c,X,Y,Z,B\}$ où $B$ est le symbole blanc.

Voici une description des transitions clés (notées (état courant, symbole lu) → (nouvel état, symbole écrit, direction)) :

1. Démarrer et marquer a:

   • (q_0, a) → (q_1, X, →): On trouve un a, on le marque X, et on part à droite chercher un b.
   • (q_0, B) → (q_a, B, |): Cas du mot vide ($n=0$), on accepte.
   • (q_0, Y) → (q_4, Y, →): On ne trouve pas de a, mais un Y. Cela signifie que tous les a ont été traités. On passe à la vérification finale.

2. Chercher et marquer b:

   • (q_1, a) → (q_1, a, →): On passe sur les a non encore traités.
   • (q_1, Y) → (q_1, Y, →): On passe sur les Y déjà marqués lors des tours précédents.
   • (q_1, b) → (q_2, Y, →): On a trouvé notre b. On le marque Y et on part chercher un c.

3. Chercher et marquer c:

   • (q_2, b) → (q_2, b, →): On passe sur les b.
   • (q_2, Z) → (q_2, Z, →): On passe sur les Z déjà marqués.
   • (q_2, c) → (q_3, Z, ←): On a trouvé notre c. On le marque Z et on entame le retour.

4. Retour au début:

   • (q_3, a|b|Y|Z) → (q_3, \text{symbole identique}, ←): On "rembobine" vers la gauche, en ignorant tout sur notre passage.
   • (q_3, X) → (q_0, X, →): On a atteint le X le plus à gauche. On se positionne juste à sa droite pour redémarrer une boucle depuis $q_0$.

5. Vérification finale:

   • (q_4, Y|Z) → (q_4, \text{symbole identique}, →): On s'assure qu'il ne reste que des Y et des Z.
   • (q_4, B) → (q_a, B, |): On a atteint la fin du ruban sans trouver de symbole inattendu. La chaîne est acceptée.

Toute transition non définie mène à un état de rejet implicite. Par exemple, si dans l'état $q_1$ on lit un c, la machine s'arrête et rejette.

3. Trace de l'exécution

Voir la machine "tourner" est le meilleur moyen de solidifier sa compréhension. Le document suivant illustre pas à pas le parcours de la tête de lecture pour l'entrée aabbcc.

Pour une vue alternative de la stratégie, la vidéo ci-dessous (en anglais) est également très pédagogique. Elle construit le diagramme d'états de manière progressive, ce qui peut vous aider à visualiser les connexions entre les états.

4. La machine complète

Après avoir conçu l'algorithme, défini les transitions et suivi une trace, nous pouvons maintenant visualiser la machine de Turing complète sous la forme d'un diagramme d'états.

Cet diagramme est la traduction graphique et formelle de notre stratégie. C'est le type d'artefact que vous devez être capable de produire.

Conclusion

Aujourd'hui, vous avez réalisé l'une des constructions les plus classiques et les plus importantes de l'informatique théorique. Ce processus de conception de machine de Turing est fondamental.

Points clés à retenir :

• La construction d'une machine de Turing commence par une stratégie algorithmique de haut niveau.
• La stratégie du "zigzag" ou du "marquage" est une technique puissante et polyvalente pour les problèmes de comptage et de mise en correspondance sur un ruban.
• Chaque étape de l'algorithme (chercher, marquer, reculer, vérifier) est implémentée par un ou plusieurs états dans la machine.
• La capacité d'écrire sur le ruban est ce qui permet à la machine de "se souvenir" des symboles qu'elle a déjà traités, dépassant ainsi la limitation de la pile d'un automate à pile.

Dans notre prochaine leçon, nous allons prendre encore plus de hauteur. Maintenant que nous savons comment construire ces puissantes machines, nous allons nous poser une question encore plus profonde, formulée par Turing lui-même : existe-t-il des problèmes qu'aucune machine de Turing ne peut résoudre ? Cela nous mènera à la notion de décidabilité et à l'un des résultats les plus célèbres de l'informatique : l'indécidabilité du problème de l'arrêt.