wingman87
05-11-2009, 14:30
Ciao a tutti, ho un dubbio riguardo la dimostrazione della tesi che non tutte le funzioni sono computabili. In particolare riguardo l'halting problem, provo a definire a grandi linee qui il problema.
Definisco la funzione totale h(x)= 1 se il programma x con input x termina e h(x)=0 se non termina. Si vuole dimostrare che non può esistere un programma che sia in grado di calcolare questa funzione.
Se h(x) fosse calcolabile potrei definire il metodo "strano" in questo modo (in pseudocodice):
strano(){
if(h(strano)==1) while(true); //strano è il codice del metodo
else return 1;
}
Giungo quindi ad un assurdo e quindi h(x) non è calcolabile.
Ora quello che non capisco è: non ho al tempo stesso dimostrato che la funzione h(x) non è definita per x=strano? Ok, non è calcolabile ma io so che se h(strano) valesse 0 sarebbe una contraddizione e lo stesso se valesse 1, quindi h(x) non è definita in strano (secondo me) e quindi non è totale. Solo che se h(x) non fosse definita in strano l'intera dimostrazione non dimostrerebbe nulla perché parte dal principio che halt sia totale mentre pare che non lo sia.
Definisco la funzione totale h(x)= 1 se il programma x con input x termina e h(x)=0 se non termina. Si vuole dimostrare che non può esistere un programma che sia in grado di calcolare questa funzione.
Se h(x) fosse calcolabile potrei definire il metodo "strano" in questo modo (in pseudocodice):
strano(){
if(h(strano)==1) while(true); //strano è il codice del metodo
else return 1;
}
Giungo quindi ad un assurdo e quindi h(x) non è calcolabile.
Ora quello che non capisco è: non ho al tempo stesso dimostrato che la funzione h(x) non è definita per x=strano? Ok, non è calcolabile ma io so che se h(strano) valesse 0 sarebbe una contraddizione e lo stesso se valesse 1, quindi h(x) non è definita in strano (secondo me) e quindi non è totale. Solo che se h(x) non fosse definita in strano l'intera dimostrazione non dimostrerebbe nulla perché parte dal principio che halt sia totale mentre pare che non lo sia.