Una macchina di Turing è un dispositivo accettante che accetta i linguaggi (insieme ricorsivamente enumerabile) generati da grammatiche di tipo 0. È stata inventata nel 1936 da Alan Turing.
Definizione
Una Macchina di Turing (TM) è un modello matematico che consiste in un nastro di lunghezza infinita diviso in celle su cui viene dato l’input. Consiste in una testa che legge il nastro di input. Un registro di stato memorizza lo stato della macchina di Turing. Dopo aver letto un simbolo di input, questo viene sostituito con un altro simbolo, il suo stato interno viene cambiato, e si sposta da una cella a destra o a sinistra. Se la TM raggiunge lo stato finale, la stringa in ingresso viene accettata, altrimenti rifiutata.
Una TM può essere formalmente descritta come una 7-tupla (Q, X, ∑, δ, q0, B, F) dove –
-
Q è un insieme finito di stati
-
X è l’alfabeto del nastro
-
∑ è l’alfabeto di ingresso
-
δ è una funzione di transizione; δ : Q × X → Q × X × {Left_shift, Right_shift}.
-
q0 è lo stato iniziale
-
B è il simbolo vuoto
-
F è l’insieme degli stati finali
Confronto con l’automa precedente
La seguente tabella mostra un confronto di come una macchina di Turing differisce dall’automa finito e dall’automa Pushdown.
| Macchina | Struttura dati stack | Deterministico? |
|---|---|---|
| Automatico finito | N.A | Sì |
| Automatismo di spegnimento | Last In First Out(LIFO) | No |
| Macchina di Turing | Nastro infinito | Sì |
Esempio di macchina di Turing
Macchina di Turing M = (Q, X, ∑, δ, q0, B, F) con
- Q = {q0, q1, q2, qf}
- X = {a, b}
- ∑ = {1}
- q0 = {q0}
- B = simbolo vuoto
- F = {qf }
δ è dato da –
| Simbolo dell’alfabeto del nastro | Stato presente ‘q0’ | Presente Stato ‘q1’ | Presente Stato ‘q2’ |
|---|---|---|---|
| a | 1Rq1 | 1Lq0 | 1Lqf |
| b | 1Lq2 | 1Rq1 | 1Rqf |
Qui la transizione 1Rq1 implica che il simbolo di scrittura è 1, il nastro si sposta a destra e lo stato successivo è q1. Allo stesso modo, la transizione 1Lq2 implica che il simbolo di scrittura è 1, il nastro si muove a sinistra, e lo stato successivo è q2.
Complessità temporale e spaziale di una macchina di Turing
Per una macchina di Turing, la complessità temporale si riferisce alla misura del numero di volte che il nastro si muove quando la macchina è inizializzata per alcuni simboli di input e la complessità spaziale è il numero di celle del nastro scritto.
Complessità temporale tutte le funzioni ragionevoli –
T(n) = O(n log n)
La complessità spaziale diTM –
S(n) = O(n)