Una macchina di Turing qualsiasi risolve un solo problema: è come un circuito progettato per un compito fisso. La macchina di Turing universale è diversa: riceve in input la descrizione di un'altra macchina e un input per essa, e ne simula il comportamento. È, in termini moderni, un interprete. L'idea che un programma possa essere trattato come un dato qualsiasi, letto ed eseguito da un altro programma, è la base sia dei computer programmabili sia di tutti i risultati di indecidibilità.
Primo passo: codificare una macchina come stringa
Per dare una macchina in input a un'altra serve rappresentarla come stringa su un alfabeto fisso. Una macchina di Turing è un oggetto finito: un numero finito di stati, simboli e transizioni. Quindi si può codificare.
Uno schema semplice sull'alfabeto {0, 1}:
- Si numerano gli stati q₁, q₂, …, qₙ, stabilendo per convenzione che q₁ sia l'iniziale, q₂ l'accettante e q₃ il rifiutante.
- Si numerano i simboli del nastro a₁, a₂, …, aₘ, con a₁ il blank.
- Si numerano le direzioni: D₁ sinistra, D₂ destra.
- Ogni transizione δ(qᵢ, aⱼ) = (qₖ, aₗ, Dₘ) si scrive come 0ⁱ 1 0ʲ 1 0ᵏ 1 0ˡ 1 0ᵐ, cioè cinque blocchi di zeri separati da un 1.
- Le transizioni si concatenano separandole con 11.
Il risultato è una stringa binaria, che si indica con ⟨M⟩. La coppia «macchina e input» si scrive ⟨M, w⟩, per esempio con un separatore 111. Lo schema specifico non è importante: conta solo che sia non ambiguo e decodificabile in modo meccanico.
Una conseguenza immediata: le macchine di Turing sono numerabili. Ogni macchina corrisponde a una stringa binaria finita, e le stringhe binarie finite si possono elencare una dopo l'altra. Questo fatto, apparentemente innocuo, sarà decisivo negli argomenti diagonali.
Secondo passo: la macchina universale
La macchina universale U riceve ⟨M, w⟩ e si comporta così:
U accetta ⟨M, w⟩ se M accetta w; rifiuta se M rifiuta w; non si ferma se M non si ferma su w.
Conviene descriverla con tre nastri, sapendo che si possono poi ridurre a uno:
- nastro del programma: contiene ⟨M⟩, la tabella delle transizioni;
- nastro di lavoro: contiene il nastro simulato di M, inizialmente w, con i simboli codificati in blocchi di zeri;
- nastro di stato: contiene la codifica dello stato corrente di M, inizialmente q₁.
Il ciclo principale di U ripete:
- legge lo stato corrente sul nastro di stato e il simbolo sotto la testina simulata sul nastro di lavoro;
- cerca sul nastro del programma la transizione che comincia con quella coppia;
- riscrive il simbolo sul nastro di lavoro, sposta la testina simulata nella direzione indicata e aggiorna il nastro di stato;
- se il nuovo stato è q₂ accetta, se è q₃ rifiuta, altrimenti ricomincia.
U è una sola macchina, con un numero fissato di stati, eppure può imitare qualsiasi altra macchina, anche con molti più stati e simboli. Il trucco è che stati e simboli di M non sono stati e simboli di U: sono stringhe scritte sui nastri di U.
Costo della simulazione
Ogni passo di M richiede a U una ricerca nella tabella delle transizioni e qualche spostamento sul nastro. Con una codifica ragionevole, il costo per passo dipende dalla dimensione di ⟨M⟩ ma non dal numero di passi già eseguiti, se si usano più nastri. Ne risulta che U simula t passi di M in un tempo dell'ordine di t moltiplicato per un fattore legato alla dimensione di M, o al più t log t con una costruzione accurata. Questo dettaglio tecnico è alla base dei teoremi di gerarchia temporale.
Il linguaggio di accettazione
L'esistenza di U mostra che il linguaggio
A_TM = {⟨M, w⟩ : M è una macchina di Turing che accetta w}
è Turing-riconoscibile: basta eseguire U. Se M accetta w, U se ne accorge dopo un numero finito di passi. Ma se M non si ferma, nemmeno U si ferma. U riconosce A_TM, ma non lo decide. Si può dimostrare che nessuna macchina lo decide: è il punto di partenza dell'indecidibilità.
Perché è un'idea così importante
- Hardware generale: invece di costruire una macchina per ogni problema, se ne costruisce una sola e le si fornisce il programma come dato. È esattamente il principio del calcolatore con programma memorizzato.
- Software che manipola software: compilatori, interpreti, emulatori, macchine virtuali e analizzatori statici sono tutti programmi che leggono altri programmi come input.
- Autoriferimento: se un programma può ricevere programmi, può anche ricevere se stesso. È questa possibilità che genera i paradossi alla base del problema dell'arresto e del teorema di Rice.
Nel mio lavoro di analisi del software questa idea è quotidiana: un malware analizzato in una sandbox, un bytecode eseguito da una macchina virtuale, uno script valutato da un interprete. Sono tutti casi in cui un programma è dato a un altro programma.
In sintesi
- Ogni macchina di Turing si codifica come stringa finita; le macchine sono quindi numerabili.
- La macchina universale U riceve ⟨M, w⟩ e simula M su w passo dopo passo.
- U ha un numero fisso di stati: stati e simboli di M sono dati scritti sui suoi nastri.
- U riconosce il linguaggio A_TM ma non lo decide.
- L'idea di programma come dato è alla base dei computer programmabili e dell'indecidibilità.
