Une machine de Turing est un dispositif d’acceptation qui accepte les langages (ensemble récursivement énumérable) générés par les grammaires de type 0. Elle a été inventée en 1936 par Alan Turing.
Définition
Une machine de Turing (MT) est un modèle mathématique qui consiste en un ruban de longueur infinie divisé en cellules sur lesquelles une entrée est donnée. Elle est constituée 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, celui-ci est remplacé par un autre symbole, son état interne est modifié et elle se déplace d’une cellule à droite ou à gauche. Si la MT atteint l’état final, la chaîne d’entrée est acceptée, sinon elle est rejetée.
Un TM peut être formellement décrit comme un 7-tuple (Q, X, ∑, δ, q0, B, F) où –
-
Q est un ensemble fini d’états
-
X est l’alphabet de bande
-
∑ est l’alphabet d’entrée
-
δ est une fonction de transition ; δ : Q × X → Q × X × {Décalage_gauche, Décalage_droit}.
-
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 façon dont une machine de Turing diffère de l’automate fini et de l’automate à poussée.
| Machine | Stack Data Structure | Déterministe ? |
|---|---|---|
| Automate fini | N.A | Oui |
| Automate à poussée | Dernier Entré Premier Sorti(LIFO) | Non |
| Machine deTuring | Bande infinie | Oui |
Exemple de machine de Turing
Machine de Turing M = (Q, X, ∑, δ, q0, B, F) avec
- Q = {q0, q1, q2, qf}
- X = {a, b}
- ∑ = {1}
- q0 = {q0}
- B = symbole vide
- F = {qf }
δ est donné par –
| Symbole de l’alphabet en bande | Présent État ‘q0’ | Présent. State ‘q1’ | Present State ‘q2’ | a | 1Rq1 | 1Lq0 | 1Lqf |
|---|---|---|---|
| b | 1Lq2 | 1Rq1 | 1Rqf |
Ici la transition 1Rq1 implique que le symbole d’écriture est 1, la bande se déplace vers la droite, et l’état suivant est q1. De même, la transition 1Lq2 implique que le symbole d’écriture est 1, que la bande se déplace vers la gauche et que l’état suivant est q2.
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 que la bande se déplace lorsque la machine est initialisée pour certains symboles d’entrée et la complexité spatiale est le nombre de cellules de la bande écrite.
Complexité temporelle toutes fonctions raisonnables –
T(n) = O(n log n)
Complexité spatiale deTM. –
S(n) = O(n)
.