Calculabilité et complexité/Machine de Turing

Leçons de niveau 17
Une page de Wikiversité, la communauté pédagogique libre.
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
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.
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 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

Variantes[modifier | modifier le wikicode]

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.