Macchina di Turing

Note

Una macchina di Turing (MT) è un modello di calcolo basato su gli automi a pila, ma con nastri di memoria.
center

Per convenzione storica e semplicità di formalizzazione, i nastri sono sequenza infinite di celle di cui:

Solo una quantità finita è inizializzata con un valore sensato
Le celle restanti contengono uno spazio vuoto o il valore blank $␢$

Tutte le testine possono scorrere su nastri o rimanere ferme

La transizione di un MT avviene in funzione di:

Lettura del carattere sotto la testina del nastro di input
Lettura dei caratteri sotto le testine dei nastri di memoria
Stato dell'organo di controllo

E può effettuare come azioni:

Cambiare lo stato dell'organo di controllo
Scrivere un carattere su ogni nastro di memoria
Scrivere un carattere sul nastro di output
Spostare le testine di memoria e ingresso: una posizione a sinistra , destra o ferme
Spostare la testina di output: una posizione a e , se si sposta si scrive sempre una lettera o un $␢$ .

Per convenzione si etichettano gli archi con formato: Con mossa della testina di input, mosse delle memorie e mossa della testina di output. Inoltre consideriamo la pila inizializzata con per marcare il fondo.

MT riconoscitore

Note

La funzione di transizione di una MT riconoscitore è definita come: $␢$

Esempio riconoscitore di

center

MT traduttore

Note

La funzione di traduzione di una MT traduttore è definita come: $␢ ␢$

Configurazione e transizione di una MT

Note

Di base, tutti i nastri di memoria sono pieni di $␢$ , tranne nella posizione iniziale della rispettiva testina, dove c'è . Si ha inoltre come stato iniziale dell'organo di controllo , e la strina di ingresso è scritta a partire della cella del nastro di ingresso, seguita e preceduta da $␢$ . Mentre il nastro di uscita è riempito con $␢$ .

Come per gli FSA e gli AP, gli stati di accettazione sono . Per convenzione, la e non sono definite a partire dagli stati finali:

Una stringa in ingresso è accettata se e solo se in un numero finito di transizioni, la macchina si ferma in .

Proprietà di una MT

Note

Si ha che una MT è chiusa a , , , , ma non al complemento.

Modelli equivalenti

Note

È possibile costruire modelli di calcolo equivalenti alla MT, tra cui:

Una MT con nastro bidimensionale
Una MT con testine per nastro
Un AP con due pile

Se un modello di calcolo può simulare una MT viene detto Turing completo. Una MT è in grado di simulare il comportamento di una macchina di Von Neumann. La differenza principale tra loro è la modalità di accesso alla memoria.

MT a nastro singolo

Una particolare variante della MT è quella a nastro singolo, dove input, output e memoria sono tutti nello stesso nastro. È in grado di emulare una MT a nastri.