Calculabilité et complexité/Machine de Turing

Début de la boite de navigation du chapitre

De façon schématique on peut représenter une machine de Turing comme une bande sur laquelle sont écrits des symboles et le long de laquelle vient pointer la tête de lecture/écriture d'une boite à états.

fin de la boite de navigation du chapitre

Représentaiton artistique d'une machine de turing.

Machine de Turing dont la tête pointe sur la lettre « a » et qui est dans l'état q₂.

$\mathrm {\textvisiblespace}$	a	b	$\mathrm {\textvisiblespace}$	ruban
	↑
	q0 q1 →q2 boite à états

Plus formellement

Définition d'une machine de Turing

Une machine de Turing est un quintuplet $M=(K,\Sigma ,\delta ,s,H)$ où :

• $K$ est un ensemble fini d'états
• $\Sigma$ est un ensemble fini de lettres (un alphabet) avec deux lettres particulières :
  • $\mathrm {\textvisiblespace}$ (l'espace, qu'on matérialisera ici par ce caractère, parfois aussi noté $b$ pour "blank") ;
  • $\triangleright$ le symbole de début de bande ;
  • notez que $\Sigma$ ne contient pas ← et → (flèches gauche et droite), les symboles de contrôle qui permettent de déplacer la tête de lecture/écriture ;
• $s\in K$ est l'état de départ ;
• $h\subset K$ est l’ensemble des états d'arrêt ;
• $\delta$ est la fonction de transition.

Plus précisément $\delta$ est définie par : $\delta :(K-H)\times \Sigma \to K\times \Sigma \cup \{\gets ,\to \}-\{\triangleright \})$ telle que $\delta (q,\triangleright )=(q',\sigma )$ implique $\sigma =\to$ (c'est-à-dire que lorsqu'on est sur $\triangleright$ on ne peut faire que $\to$).

Exemples : $M=(K,\Sigma ,\delta ,s,{h})$ avec :

• $K=\{q_{0},q_{1},h\}$ ;
• $\Sigma =\{a,\mathrm {\textvisiblespace} ,\triangleright \}$ ;
• $s=q_{0}$

Représentation matricielle de $\delta$

		$\sigma$
		$\triangleright$	$\mathrm {\textvisiblespace}$	$a$
$K$	$q_{0}$	$(q_{0},\to )$	$(h,\mathrm {\textvisiblespace} )$	$(q_{1},\mathrm {\textvisiblespace} )$
	$q_{1}$	$(q_{1},\to )$	$(q_{1},\to )$	$(q_{0},a)$

Exemple d'application de la machine sur un ruban

Étape	Représentation de l'image de la machine.
Étape 0	$\triangleright$	a	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
	↑ $q_{0}$
Étape 1	$\triangleright$	a	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
		↑ $q_{0}$
Étape 2	$\triangleright$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
		↑ $q_{1}$
Étape 3	$\triangleright$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
			↑ $q_{0}$
Étape 4	$\triangleright$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
			↑ $q_{1}$
Étape 5	$\triangleright$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
				↑ $q_{0}$
Étape 6	$\triangleright$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
				↑ $q_{1}$
Étape 7	$\triangleright$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
					↑ $q_{0}$
Étape 8	$\triangleright$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	a	a	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$	$\mathrm {\textvisiblespace}$
					↑ $h$

Variantes

Diverses variantes des machines de Turing existe. Parmi les variations on distingue notamment :

• la possibilité d'écrire et déplacer la tête de lecture en même temps ;
• l'absence du symbole $\triangleright$ ;
• l’utilisation d'une bande infinie à droite et à gauche ;
• l’existence de symboles de contrôle, souvent noté $ ou €, n'appartenant pas à $\Sigma$ ;
• l’utilisation d'un ruban à plusieurs dimensions ;
• etc.