Problema della terminazione
Il problema della fermata o problema dell'arresto è un problema proposto nel 1937, insieme alla dimostrazione della sua indecidibilità, dal matematico Alan Turing. Nel problema si chiede se sia sempre possibile, descritto un programma e un determinato input finito, stabilire se il programma in questione termini o si ripeta all'infinito. È stato dimostrato che non può esistere un algoritmo generale che possa risolvere il problema per tutti i possibili input.
Dimostrazione
Consideriamo un generico programma, che chiameremo A, e dei generici dati in ingresso, che chiameremo D. Supponiamo per assurdo l'esistenza di un programma che chiameremo C che, dati in ingresso A e D, restituisca 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 a decidere se i dati siano accettabili o meno, non è questo il punto focale del problema) li mandiamo in esecuzione nel programma, cioè C(A,A).
Otteniamo un nuovo programma, che chiameremo Paradosso, così fatto:
Paradosso(A): while (C (A,A));
Il programma Paradosso termina solamente se la guardia C(A,A) restituisce il valore false ovvero se il programma A con input A non termina.
Infine passiamo Paradosso come argomento al programma Paradosso:
Paradosso (Paradosso) : while (C (Paradosso,Paradosso));
Questo programma 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.