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!
Leggi il resto di questo articolo »