Calculabilité et complexité/Machine de Turing

Début de la boite de navigation du chapitre
Machine de Turing
Icône de la faculté
Chapitre no 3
Leçon : Calculabilité et complexité
Chap. préc. :Rappel sur la notion de langage
Chap. suiv. :Méthodologies de mise en œuvre
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Calculabilité et complexité : Machine de Turing
Calculabilité et complexité/Machine de Turing
 », n'a pu être restituée correctement ci-dessus.

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.

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 q2.
a b ruban
q0
 q1
→q2
boite à états


Plus formellement


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 :

  •  ;
  •  ;


Représentation matricielle de


Exemple d'application de la machine sur un ruban
É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

VariantesModifier

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 à   ;
  • l’utilisation d'un ruban à plusieurs dimensions ;
  • etc.