Problema della fermata
Da Wikipedia, l'enciclopedia libera.
Il problema della fermata fu pubblicato nel 1937 dal matematico Alan Turing. Consiste nel capire se un generico programma termina o entra in un ciclo infinito.
- Per dimostrarlo prendiamo un generico programma che chiameremo A e dei generici dati in ingresso che chiameremo D e supponiamo per assurdo l'esistenza di un programma che chiameremo TERMINA che, dati in ingresso A e D, restituisca il valore TRUE se termina e FALSE se non termina.
TERMINA (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è TERMINA (A,A).
Otteniamo un nuovo programma che chiameremo PARADOSSO, così fatto:
PARADOSSO (A) : while (TERMINA (A,A));
- Il programma PARADOSSO termina solamente se la guardia TERMINA(A,A) restituisce il valore FALSE ovvero se il programma TERMINA(A,A) non termina.
Infine passiamo PARADOSSO come argomento al programma PARADOSSO:
PARADOSSO (PARADOSSO) : while (TERMINA (PARADOSSO,PARADOSSO);
- Questo programma termina ancora una volta solo se la guardia TERMINA(PARADOSSO,PARADOSSO) è falsa.
Ma se la guardia è falsa se ne deduce che PARADOSSO(PARADOSSO) termina solo quando non termina e questa è una contraddizione.
