Problema della terminazione

Il problema della terminazione (dall'inglese Halting problem, tradotto anche con problema dell'arresto o problema della fermata) chiede se sia sempre possibile, descritto un algoritmo e un determinato input finito, stabilire se l'algoritmo in questione termini o continui la sua esecuzione all'infinito. È stato dimostrato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input. La versione più nota del problema è quella proposta nel 1937 dal matematico Alan Turing, insieme alla dimostrazione della sua indecidibilità.

Dimostrazione

Consideriamo un generico algoritmo, che chiameremo A, e dei generici dati in ingresso, che chiameremo D. Supponiamo per assurdo l'esistenza di un altro algoritmo che chiameremo C e che, dati in ingresso A e D, calcola se l'algoritmo A si conclude in un tempo finito, restituendo il valore true se termina e false se non termina.

C(A, D) = true se termina, false se non termina.

Essendo sia A che D sequenze indistinte di simboli per la macchina, possiamo immaginare che A rappresenti dati in ingresso senza tener conto della loro coerenza (sarà infatti il programma che esegue l'algoritmo C a decidere se i dati siano accettabili o meno e ad interpretarli come programma o dato) e quindi possiamo mandarli in esecuzione come C(A,A).

Si consideri ora quest'altro algoritmo, che chiameremo Paradosso, così fatto:

Paradosso(A): while (C (A,A));

L'algoritmo Paradosso termina solamente se la guardia C(A,A) restituisce il valore false ovvero se l'algoritmo A con input A non termina.

Infine passiamo Paradosso come argomento all'algoritmo Paradosso:

Paradosso (Paradosso) : while (C (Paradosso,Paradosso));

Questo algoritmo termina ancora una volta solo se la guardia C(Paradosso,Paradosso) è falsa. Ma se la guardia è falsa se ne deduce che Paradosso(Paradosso) termina solo quando non termina e questa è una contraddizione.

Relazioni con altri teoremi

Il teorema di Rice è una versione più generale del teorema che afferma che il problema della fermata è indecidibile. Infatti, esso afferma che, per ogni proprietà non banale delle funzioni parziali, è indecidibile il problema di determinare quali funzioni soddisfino tale proprietà e quali no.