Sarebbe comodo avere uno strumento che, dato un programma qualsiasi e un suo input, dica se il programma prima o poi termina oppure resta in ciclo per sempre. Un tale strumento troverebbe automaticamente tutti i cicli infiniti, e molto altro. Il problema della fermata (halting problem) chiede esattamente questo, e la risposta della teoria è netta: un algoritmo del genere non può esistere. Non per mancanza di potenza di calcolo, ma per una contraddizione logica.
La formulazione precisa
Il linguaggio della fermata è:
HALT_TM = {⟨M, w⟩ : M è una macchina di Turing che si ferma sull'input w}
Strettamente collegato è il linguaggio di accettazione:
A_TM = {⟨M, w⟩ : M accetta w}
Il teorema afferma che entrambi sono indecidibili: non esiste una macchina di Turing che, su ogni input ⟨M, w⟩, si fermi sempre e risponda correttamente. Entrambi sono però riconoscibili: basta simulare M su w con la macchina universale e aspettare.
La dimostrazione per A_TM
Dimostriamo prima che A_TM è indecidibile, con un argomento per assurdo.
Supponiamo che esista un decisore H tale che:
- H(⟨M, w⟩) accetta se M accetta w;
- H(⟨M, w⟩) rifiuta se M non accetta w (perché rifiuta o perché non si ferma).
H si ferma sempre, per ipotesi.
Costruiamo una nuova macchina D che riceve in input la descrizione ⟨M⟩ di una macchina:
- esegue H sull'input ⟨M, ⟨M⟩⟩, cioè chiede se M accetta la propria descrizione;
- se H accetta, D rifiuta;
- se H rifiuta, D accetta.
D si ferma sempre, perché H si ferma sempre. Fa l'opposto di ciò che M farebbe su se stessa.
Ora diamo a D la sua stessa descrizione, ⟨D⟩:
- se D accetta ⟨D⟩, allora H(⟨D, ⟨D⟩⟩) ha accettato, quindi per costruzione D rifiuta ⟨D⟩;
- se D rifiuta ⟨D⟩, allora H(⟨D, ⟨D⟩⟩) ha rifiutato, quindi per costruzione D accetta ⟨D⟩.
In entrambi i casi otteniamo una contraddizione. Quindi H non può esistere, e A_TM è indecidibile.
Perché si chiama diagonalizzazione
Immaginiamo una tabella infinita. Le righe sono tutte le macchine di Turing M₁, M₂, M₃, …, che sappiamo essere numerabili. Le colonne sono le loro descrizioni ⟨M₁⟩, ⟨M₂⟩, ⟨M₃⟩, … Nella cella (i, j) scriviamo «accetta» se Mᵢ accetta ⟨Mⱼ⟩, altrimenti «non accetta».
La macchina D è costruita in modo da comportarsi, sulla colonna i, all'opposto di quanto indicato nella cella diagonale (i, i). Dunque D differisce da ogni macchina Mᵢ almeno su un input, ⟨Mᵢ⟩. Ma D è una macchina di Turing, quindi dovrebbe comparire in qualche riga: contraddizione. È lo stesso schema con cui si dimostra che i numeri reali non sono numerabili.
Dalla accettazione alla fermata
Ora mostriamo che anche HALT_TM è indecidibile, con una riduzione. Supponiamo che esista un decisore R per HALT_TM. Allora potremmo decidere A_TM così, su input ⟨M, w⟩:
- si esegue R su ⟨M, w⟩;
- se R dice che M non si ferma su w, si rifiuta: M certamente non accetta;
- se R dice che M si ferma, si simula M su w, sapendo che la simulazione terminerà, e si risponde come M.
Avremmo un decisore per A_TM, che non esiste. Quindi R non esiste.
Un linguaggio nemmeno riconoscibile
Un linguaggio è decidibile se e solo se sia esso sia il suo complemento sono riconoscibili: basta eseguire in parallelo i due riconoscitori e aspettare che uno dei due accetti. Poiché A_TM è riconoscibile ma non decidibile, il suo complemento non è nemmeno riconoscibile. Esistono quindi problemi per cui non si può neppure garantire di confermare tutte le risposte positive.
Che cosa significa davvero, e che cosa no
L'indecidibilità viene spesso fraintesa. Alcune precisazioni:
- Non significa che non si possa sapere se un programma specifico termina. Per moltissimi programmi concreti lo si dimostra senza difficoltà.
- Significa che non esiste un unico algoritmo che dia la risposta corretta per tutti i programmi.
- Gli strumenti reali di analisi statica aggirano il limite in modo onesto: rispondono «termina», «non termina» oppure «non so», oppure limitano il linguaggio analizzato, oppure accettano falsi allarmi.
- Un timeout non risolve il problema: se un programma non ha ancora finito, non sappiamo se finirà tra un secondo o mai.
Nel mio lavoro questo limite si vede bene nell'analisi del codice sospetto: nessuno strumento può stabilire con certezza, in ogni caso, che cosa farà un programma su tutti gli input. Ci si affida quindi a combinazioni di analisi statica, esecuzione controllata e giudizio umano.
In sintesi
- Il problema della fermata chiede se una macchina si ferma su un input; non esiste un algoritmo che lo decida sempre.
- La dimostrazione costruisce una macchina D che contraddice se stessa quando riceve la propria descrizione.
- È un argomento di diagonalizzazione, lo stesso che mostra la non numerabilità dei reali.
- A_TM e HALT_TM sono riconoscibili ma non decidibili; i loro complementi non sono neppure riconoscibili.
- L'indecidibilità riguarda un algoritmo universale, non i singoli programmi.
