Calculabilité et complexité/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.

a | b | ruban | ||
↑ | ||||
q0
q1→q2 boite à états
|
Plus formellement
Définition d'une machine de Turing
Une machine de Turing est un quintuplet où :
- est un ensemble fini d'états
- est un ensemble fini de lettres (un alphabet) avec deux lettres particulières :
- (l'espace, qu'on matérialisera ici par ce caractère, parfois aussi noté pour "blank") ;
- le symbole de début de bande ;
- notez que 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 ;
- est l'état de départ ;
- est l’ensemble des états d'arrêt ;
- est la fonction de transition.
Plus précisément est définie par :
telle que implique (c'est-à-dire que lorsqu'on est sur on ne peut faire que
).
Exemples : avec :
- ;
- ;
Étape | Représentation de l'image de la machine. | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Étape 0 | a | a | a | a | a | |||||||
↑ |
||||||||||||
Étape 1 | a | a | a | a | a | |||||||
↑ | ||||||||||||
Étape 2 | a | a | a | a | ||||||||
↑ | ||||||||||||
Étape 3 | a | a | a | a | ||||||||
↑ | ||||||||||||
Étape 4 | a | a | a | |||||||||
↑ | ||||||||||||
Étape 5 | a | a | a | |||||||||
↑ | ||||||||||||
Étape 6 | a | a | ||||||||||
↑ | ||||||||||||
Étape 7 | a | a | ||||||||||
↑ | ||||||||||||
Étape 8 | a | a | ||||||||||
↑ |
Variantes
modifierDiverses 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 à ;
- l’utilisation d'un ruban à plusieurs dimensions ;
- etc.