Présentation de la machine de Turing

Une machine de Turing est un appareil accepteur qui accepte les langues (ensemble récursivement énumérable) générées par les grammaires de type 0. Il a été inventé en 1936 par Alan Turing.

Définition

Une machine de Turing (TM) est un modèle mathématique qui consiste en une bande de longueur infinie divisée en cellules sur lesquelles une entrée est donnée. Il se compose d'une tête qui lit la bande d'entrée. Un registre d'état stocke l'état de la machine de Turing. Après avoir lu un symbole d'entrée, il est remplacé par un autre symbole, son état interne est modifié et il se déplace d'une cellule vers la droite ou la gauche. Si la TM atteint l'état final, la chaîne d'entrée est acceptée, sinon rejetée.

Un TM peut être formellement décrit comme un 7-tuple (Q, X, ∑, δ, q 0 , B, F) où -

  • Q est un ensemble fini d'états

  • X est l'alphabet de la bande

  • ∑ est l'alphabet d'entrée

  • δest une fonction de transition; δ: Q × X → Q × X × {Left_shift, Right_shift}.

  • q0 est l'état initial

  • B est le symbole vide

  • F est l'ensemble des états finaux

Comparaison avec l'automate précédent

Le tableau suivant montre une comparaison de la différence entre une machine de Turing et un automate fini et un automate pushdown.

Machine Structure des données de la pile Déterministe?
Automate fini N / A Oui
Automaton Pushdown Dernier entré, premier sorti (LIFO) Non
Machine de Turing Bande infinie Oui

Exemple de machine de Turing

Machine de Turing M = (Q, X, ∑, δ, q 0 , B, F) avec

  • Q = {q 0 , q 1 , q 2 , q f }
  • X = {a, b}
  • ∑ = {1}
  • q 0 = {q 0 }
  • B = symbole vide
  • F = {q f }

δ est donné par -

Symbole de l'alphabet de bande État actuel 'q 0 ' État actuel 'q 1 ' État actuel 'q 2 '
une 1Rq 1 1Lq 0 1Lq f
b 1Lq 2 1Rq 1 1Rq f

Ici, la transition 1Rq 1 implique que le symbole d'écriture est 1, la bande se déplace vers la droite et l'état suivant est q 1 . De même, la transition 1Lq 2 implique que le symbole d'écriture est 1, la bande se déplace vers la gauche et l'état suivant est q 2 .

Complexité temporelle et spatiale d'une machine de Turing

Pour une machine de Turing, la complexité temporelle fait référence à la mesure du nombre de fois où la bande se déplace lorsque la machine est initialisée pour certains symboles d'entrée et la complexité de l'espace est le nombre de cellules de la bande écrites.

Complexité temporelle toutes les fonctions raisonnables -

T(n) = O(n log n)

Complexité spatiale de TM -

S(n) = O(n)