La definizione standard di macchina di Turing prevede un solo nastro, una sola testina e un comportamento deterministico. Ci si può chiedere se queste scelte limitino il modello. La risposta è no: molte varianti apparentemente più potenti riconoscono esattamente gli stessi linguaggi. Dimostrarlo è utile per due motivi. Primo, conferma che il concetto di calcolabilità non dipende da dettagli tecnici. Secondo, ci autorizza a usare la variante più comoda in ogni dimostrazione.
Lo schema generale: simulare
Per mostrare che una variante V non è più potente del modello base B basta dimostrare che ogni macchina di tipo V può essere simulata da una macchina di tipo B. Simulare significa che B, sullo stesso input, accetta, rifiuta o non si ferma esattamente come V. Il viceversa di solito è banale, perché il modello base è un caso particolare della variante.
Nastro infinito in entrambe le direzioni
Nella definizione base il nastro ha un inizio. Una variante ammette un nastro infinito sia a sinistra sia a destra.
Simulazione: si «piega» il nastro bidirezionale su quello unidirezionale. Le celle con indice 0, 1, 2, … finiscono nelle posizioni pari, quelle con indice −1, −2, … nelle posizioni dispari. Uno stato in più ricorda su quale metà si trova la testina, e ogni spostamento diventa un salto di due celle nella direzione opportuna. In alternativa si usano tracce: l'alfabeto del nastro contiene coppie di simboli, una per metà.
Macchine multinastro
Una macchina a k nastri ha k testine indipendenti; la transizione legge k simboli, ne scrive k e sposta ogni testina.
Simulazione con un solo nastro:
- Si scrive il contenuto dei k nastri uno dopo l'altro, separati da un simbolo #.
- La posizione di ogni testina si segna con una versione «puntata» del simbolo che sta sotto di essa (per esempio, 0̇ al posto di 0).
- Per simulare un passo, la macchina scorre tutto il nastro per leggere i k simboli puntati, poi lo scorre di nuovo per aggiornarli e spostare i punti.
- Se una testina deve avanzare oltre la fine della sua sezione, si spostano a destra di una cella tutti i contenuti successivi per fare spazio.
Costo: se la macchina multinastro impiega t passi, ciascun nastro contiene al massimo O(t) simboli, quindi la simulazione di un passo richiede O(t) passi e quella complessiva O(t²). Il rallentamento è polinomiale (quadratico): per questo la classe P è la stessa con uno o con più nastri.
Macchine non deterministiche
In una macchina non deterministica δ restituisce un insieme di possibili mosse. Il calcolo è un albero: ogni nodo è una configurazione, i figli sono le configurazioni raggiungibili in un passo. La macchina accetta se esiste un ramo che raggiunge lo stato di accettazione.
Simulazione deterministica: si esplora l'albero in ampiezza. Non in profondità, perché un ramo infinito bloccherebbe la ricerca e un ramo accettante altrove non verrebbe mai trovato.
Una costruzione classica usa tre nastri:
- il primo conserva l'input, mai modificato;
- il secondo è il nastro di lavoro su cui si simula un singolo ramo;
- il terzo contiene un «indirizzo», una sequenza di scelte (per esempio 2, 1, 3) che individua un nodo dell'albero.
Per ogni indirizzo, in ordine di lunghezza crescente, si copia l'input sul nastro di lavoro e si simula il ramo seguendo le scelte indicate. Se un ramo accetta, si accetta.
Costo: se ogni configurazione ha al massimo b scelte e il ramo accettante più corto ha lunghezza t, la simulazione può richiedere un tempo dell'ordine di bᵗ, cioè esponenziale. Nessuno sa se si possa fare molto meglio in generale: questa è, in forma tecnica, la questione P vs NP.
Enumeratori
Un enumeratore è una macchina di Turing collegata a una stampante: non riceve input, lavora e di tanto in tanto stampa una stringa. Il linguaggio enumerato è l'insieme delle stringhe stampate prima o poi, eventualmente con ripetizioni e in qualsiasi ordine.
Vale il teorema:
un linguaggio è Turing-riconoscibile se e solo se esiste un enumeratore che lo enumera.
- Da enumeratore a riconoscitore: data w, si esegue l'enumeratore e si confronta ogni stringa stampata con w; se coincidono, si accetta.
- Da riconoscitore a enumeratore: non si può semplicemente eseguire il riconoscitore su una stringa dopo l'altra, perché potrebbe non fermarsi su una di esse. Si usa invece la tecnica a coda di rondine (dovetailing): per i = 1, 2, 3, … si eseguono i passi sulle prime i stringhe, ciascuna per i passi, e si stampa ogni stringa accettata. Così ogni stringa del linguaggio viene stampata dopo un tempo finito.
Questa seconda costruzione è il motivo del nome «ricorsivamente enumerabili».
Che cosa non cambia e che cosa sì
| Variante | Linguaggi riconosciuti | Costo della simulazione |
|---|---|---|
| Nastro bidirezionale | Gli stessi | Lineare |
| k nastri | Gli stessi | Quadratico |
| Non determinismo | Gli stessi | Esponenziale (con le tecniche note) |
| Enumeratore | Gli stessi | Non pertinente |
La calcolabilità è invariante; la complessità no. Questa distinzione è il ponte fra le due grandi parti della teoria.
In sintesi
- Per confrontare due modelli si mostra che ognuno può simulare l'altro.
- Nastro bidirezionale e più nastri non aggiungono potere, e costano al massimo un rallentamento quadratico.
- Le macchine non deterministiche si simulano esplorando in ampiezza l'albero dei calcoli, con costo esponenziale noto.
- Gli enumeratori caratterizzano i linguaggi Turing-riconoscibili, grazie alla tecnica a coda di rondine.
- Le varianti lasciano invariata la calcolabilità ma possono cambiare la complessità.
