Les modèles du calculable: la machine de Turing

Définition

Un alphabet fini S={s0,s1,...}, contenant au moins 2 symboles.

Un ensemble fini d'états caractérisés par des symboles {q0,q1,...qn}.

Une bande infinie, sur laquelle peuvent être écrits des symboles appartenant à l'alphabet.

Une tête de lecture-écriture pouvant se déplacer sur la bande d'une position à la fois, dans un sens (G) ou dans l'autre (D).

La figure en donne une représentation schématique.

Un programme pour une machine de Turing est un ensemble fini de quadruplets de la forme (s,qi,a,qf):

1. un symbole de l'alphabet s
2. un état de la machine qi
3. une action de déplacement (G ou D) ou d'écriture sur la bande d'un symbole de l'alphabet.
4. un état interne qf

Quand la machine lit le symbole s, et qu'elle est dans l'état qi, elle réalise l'action a et passe dans l'état qf. Le symbole s et l'état qi constituent le préfixe du quadruplet, l'action a et l'état qf constituent le suffixe.

Une machine de Turing est dite déterministe quand les préfixes des quadruplets d'un programme sont tous différents.

Exemple:

• 4 états {q0,q1,q2,q3}
• 2 caractères {a,B}
• état initial q0
• Programme: (q0 B G q1) (q1 a G q1) (q1 B a q2) (q2 a D q2) (q2 B G q3) (q3 a B q3)

Question: que fait ce programme? Prendre comme bande initiale BaaaBaaaaaB.

Remarquer que (q3 a B q3) est nécessairement terminal. Mais ce n'est pas le seul moyen d'arrêter une machine de Turing.

Résultats:

Toute machine non déterministe peut être, par un programme de machine de Turing, ramenée à une machine déterministe. Il suffit de "répliquer" le graphe des états.

L'arrêt d'un programme est indécidable:

• une machine étant donnée avec son programme, la machine s'arrête-t-elle pour la donnée n?
• on convient que la donnée n est "n fois a entouré de B".
• si l'on note les symboles et les états par des nombres, un nombre fini de symboles permet de représenter toute machine ( ) " " 0 1 2 3 4 5 6 7 8 9 D G
• Les machines de Turing sont énumérables, donc numérotables.
• existe-t-il une machine de Turing MA qui, si l'on écrit une machine M sur sa bande suivi de la donnée n, telle que MA s'arrête en écrivant "oui" si M s'arrête pour la donnée n, et "non" dans le cas contraire.
• si oui, on pourrait construire MB qui, à partir de n, donne la définition de la machine numérotée n suivi de n comme donnée, puis se comporte comme MA et, à la fin, s'arrête si MA répond "non" et boucle si MA répond "oui".
• que se passe-t-il si on donne comme donnée à MB son propre numéro?

Autre exemple (plus simple):

• 4 états {q0,q1,q2,q3}
• 2 caractères {a,B}
• état initial q0
• Programme: (q0 B G q0) (q0 a G q1) (q1 a G q1) (q1 B a q2) (q2 a G q2) (q2 B a q3) (q3 a G q3)

Question: que fait ce programme? Prendre comme bande initiale BBBBaaaB.

Autre exemple (plus difficile, qui montre la notion de "symbole non terminal"):

• 4 états {q0,q1,q2,q3,q4,q5}
• 4 caractères {a,2,3,B}
• état initial q0
• Programme:
  • (q0 B G q0) (q0 3 D q4) (q0 a 2 q1)
  • (q1 a G q1) (q1 B 3 q2) (q1 3 G q1)
  • (q2 3 G q2) (q2 B 3 q3)
  • (q3 a D q3) (q3 3 D q3) (q3 2 G q0)
  • (q4 B G q5) (q4 2 D q4)
  • (q5 2 a q5) (q5 3 a q5) (q5 a G q1)

Question: que fait ce programme? Prendre comme bande initiale BBBBBaaB.