Macchine di Turing

La discussione che segue è informale, e serve a dare indicazioni su cosa sono e come si comportano le macchine di Turing.

Una macchina di Turing è composta, come un DFA, da un insieme di stati e da una sequenza di input i cui "caratteri" sono quelli previsti da un alfabeto.

Anche le macchine di Turing hanno uno stato iniziale, ma in più - rispetto a una DFA - hanno anche un "nastro" su cui possono essere memorizzate delle informazioni.

Siccome le TM devono essere più semplici possibile, anche il nastro ha un funzionamento estremamente semplice: è una striscia discreta (cioè si passa da 1 a 2, da 2 a 3 eccetera, senza posizioni intermedie come 1/2) che può memorizzare un carattere per cella da un insieme di caratteri predefiniti. La TM ha una testina che legge e scrive un carattere alla volta e si può spostare a destra o a sinistra di una sola posizione alla volta.

I caratteri di input sono un sottoinsieme dei caratteri possibili nel nastro (in teoria possono anche coincidere, ma nella pratica servono caratteri aggiuntivi nel nastro).

Anche il passaggio da uno stato all'altro è discreto, come, in un calcolatore moderno, un clock fa passare una CPU da uno stato all'altro in maniera virtualmente discreta.

Il nastro è illimitato, ha una fine a sinistra e solitamente è marcato da un ˽ (blank) a destra.

Per quanto riguarda l'insieme di funzioni δ che cambiano di stato la TM, δ prende in ingresso lo stato corrente e il carattere del nastro (lettura) e fa questo:

1. cambia di stato la TM
2. scrive un carattere sul nastro nella posizione corrente
3. si sposta a destra o a sinistra

Formalmente, si scrive δ(q_i, b) = (q_j, c, R), dove q_i e q_j sono stati della TM, b, c sono caratteri del nastro e L|R indica se la testina si sposta a destra o a sinistra.

Una TM può terminare la sua elaborazione in uno stato considerato accepted o in uno stato considerato rejected, e con questi due abbiamo completato tutto ciò che serve per definire completamente una TM.

In aggiunta, una TM può non terminare mai (per esempio se diciamo di andare avanti e indietro sulla stessa posizione all'infinito). Salvo casi banali, decidere se una macchina sta ancora lavorando ma arriverà a q_accepted o q_rejected oppure se lavorerà all'infinito senza arrivare mai a uno stato finale è un problema importante.

Limitare a sinistra

Mentre a destra la macchina può scorrere il nastro all'infinito e marcare la fine (provvisoria) del nastro con un carattere di terminazione ˽, a sinistra si ferma una volta arrivato alla posizione iniziale. Siccome vogliamo che la macchina sia più semplice possibile, anche a discapito della quantità di lavoro che deve fare, per capire quando arriva a sinistra può scrivere un carattere speciale nella posizione corrente e tentare di andare a sinistra: se ci riesce, torna indietro, ripristina il carattere originale e poi di nuovo a sinistra; se invece trova di nuovo il carattere speciale significa che il tentativo di andare a sinistra è stato bloccato dal limite della TM e quindi in effetti è all'inizio del nastro.

Macchina multi nastro

Se immaginiamo una macchina di Turing con più di un nastro, sembra che questa sia più "potente" di una TM con un nastro solo, ma non è così: per rendere une TM multinastro equivalente a una TM a nastro singolo, è sufficiente creare una TM con un simbolo in più per delimitare la fine di ogni "nastro virtuale" e raddoppiare ciascun alfabeto per introdurre un insieme di simboli che rappresentano il posto in cui si trova la testina.

Da un punto di vista "alto livello", tra un delimitatore e l'altro si troveranno una serie di simboli appartenenti al "multinastro" originale, in più uno dei caratteri avrà un "pallino" sopra. Solo un carattere, nella sequenza delimitata, avrà il pallino, perché indica la posizione della testina, che è una sola.

La TM che otterremo sarà molto più articolata e macchinosa dell'originale, ma dal punto di vista potenziale è perfettamente equivalente.

Macchina nondeterministica

Per far funzionare una TM nondeterministica, è necessario creare un branch per ciascuna delle possibili configurazioni, ma il problema è che se entriamo in uno dei rami con una modalità depth-first rischiamo di ritrovarci in un loop di sotto-branch infinito, mancando di rilevare qualche ramo che potrebbe essere finito.

Allora la strategia migliore è breadth first (visita in ampiezza).

Creando una TM con tre nastri, uno di input, uno di simulazione e uno di indirizzi, che indica quale simulazione stiamo valutando, otterremo una TM deterministica equivalente alla TM nondeterministica (come sempre, più elaborata, ma equivalente).

Siccome abbiamo dimostrato in precedenza che una TM multinastro è equivalente a una TM mononastro, per transitività anche una TM nondeterministica è equivalente a una TM monostrato deterministica.

Enumeratore

Un enumeratore è una macchina di Turing con una stampante collegata.

è equivalente a una macchina di Turing.