Calculabilité et complexité/Machine de Turing

Représentaiton artistique d'une machine de turing.

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.

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

$␣$	a	b	$␣$	ruban
	↑
	q0 q1 →q2 boite à états

Plus formellement Modèle:Définition

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

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

• $K=\{q_0,q_1,h\}$ ;
• $\mathrm{\Sigma }=\{a,␣,▹\}$ ;
• $s=q_0$

Modèle:Entête tableau charte |+ Représentation matricielle de $\delta$ | bgcolor="#ffffff" rowspan="2" colspan="2" | !colspan="3"|$\sigma$ |- !align="center" bgcolor="#CCCCCC"|$▹$ !align="center" bgcolor="#CCCCCC"|$␣$ !align="center" bgcolor="#CCCCCC"|$a$ |- !align="center" bgcolor="#CCCCCC" rowspan="2"|$K$ !align="center" bgcolor="#CCCCCC" |$q_0$ |$(q_0,\to )$ |$(h,␣)$ |$(q_1,␣)$ |- !align="center" bgcolor="#CCCCCC" |$q_1$ |$(q_1,\to )$ |$(q_1,\to )$ |$(q_0,a)$ |}

Modèle:Entête tableau charte |+Exemple d'application de la machine sur un ruban ! Étape ! colspan="12"|Représentation de l'image de la machine. |- |rowspan="2"|Étape 0 |$▹$ |a |a |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- |align="center"|↑
$q_0$ | | | | | | | | | | | |- |rowspan="2"|Étape 1 |$▹$ |a |a |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | |align="center"|↑
$q_0$ |- |rowspan="2"|Étape 2 |$▹$ |$␣$ |a |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | |align="center"|↑
$q_1$ |- |rowspan="2"|Étape 3 |$▹$ |$␣$ |a |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | |align="center"|↑
$q_0$ |- |rowspan="2"|Étape 4 |$▹$ |$␣$ |$␣$ |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | |align="center"|↑
$q_1$ |- |rowspan="2"|Étape 5 |$▹$ |$␣$ |$␣$ |a |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | | |align="center"|↑
$q_0$ |- |rowspan="2"|Étape 6 |$▹$ |$␣$ |$␣$ |$␣$ |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | | |align="center"|↑
$q_1$ |- |rowspan="2"|Étape 7 |$▹$ |$␣$ |$␣$ |$␣$ |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | | | |align="center"|↑
$q_0$ |- |rowspan="2"|Étape 8 |$▹$ |$␣$ |$␣$ |$␣$ |$␣$ |$␣$ |a |a |$␣$ |$␣$ |$␣$ |$␣$ |- | | | | |align="center"|↑
$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 $▹$ ;
• l’utilisation d'une bande infinie à droite et à gauche ;
• l’existence de symboles de contrôle, souvent noté $ ou €, n'appartenant pas à $\mathrm{\Sigma }$ ;
• l’utilisation d'un ruban à plusieurs dimensions ;
• etc.