Macchina di Turing

Note

Una macchina di Turing (MT) è un modello di calcolo basato su gli automi a pila, ma con nastri di memoria. 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

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.