i n f o r m a t i x

HALT NON ESISTE

E’ impossibile scrivere un programma che dato in input un’altro programma ed il suo input dica se questo termina oppure cicla all’infinito.

In termini un po’ più formali: non esiste un algoritmo (e quindi una funzione calcolabile) H che data in input la rappresentazione di un altro algoritmo (e quindi ancora una funzione calcolabile) A e di un’input I di A ci dice se A termina o meno su I.

Nota: La rappresentazione di un algoritmo come dato (quindi numero) è sempre possibile ed alcuni la chiamano Godelizzazione.

Dimostriamolo!

Supponiamo che esista l’algoritmo H siffatto:


H(A,I) = 'yes' se A termina su I
H(A,I) = 'no' se A non termina (cicla all'infinito) su I


Ora prendiamo un algoritmo T così definito:


function T(r) {
if ( halt(r,r)=='no' )
return 'yes';
else
while (true) ;
}


Ora vediamo cosa succede richiamando H con T sia come primo che secondo parametro (questo è perfettamente lecito grazie alla nota sopra che ci dice che una rappresentazione di un algoritmo può esser vista come un dato):


1) se H(T,T) == 'yes' allora si avrebbe una contraddizione in quanto vorrebbe dire che T termina su T ma in realtà dallo pseudocodice di T possiamo vedere che T va in loop infinito (while(true)).
2) se H(T,T) == 'no' allora si avrebbe un'altra contraddizione in quanto vorrebbe dire che T non termina su T ma in realtà, sempre dallo pseucodice di T, possiamo vedere che in questo caso T termina ritornando 'yes' (sarebbe andato bene anche un valore qualsiasi, basta che terminava).