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)