Dove $varphi_n$ è una enumerazione di una classe di funzioni parziali. (L’idea intuitiva é quella di immaginare di avere una enumerazione di agenti di calcolo o programmi $P_i$ e che $varphi _i$ sia il la funzione calcolata dal programma dall’i-esimo programma P i . In generale avremo che una stessa funzione puó essere calcolata da più programmi, dunque la funzione $varphi _i$ di enumerazione non é in generale iniettiva: $varphi _i = varphi _j$ non implica i = j (due programmi possono calcolare la stessa funzione ma essere differenti).
Intuitivamente la funzione non è calcolabile perchè $varphi _i$ potrebbe divergere prima di arrivare a n minimo. Dovrei riuscire a costruire una funzione per ridurre il problema della terminazione a questo. Il punto è che mi è poco chiaro come costruire questa funzione. ho pensato a $varphi_(h(x))(n) = g(x,n)={ (0 if n>0),( 0 if n=0 and varphi_x(x)darr ) ,(uarr if varphi_x(x)uarr):}$. Per il teorema s.m.n, h(x) esiste ed è intuitivamente calcolabile (ad esempio uso un algoritmo del tipo:
- Codice:
IF (n>o)
return 0
ELSE
$varphi_x(x)$; //eseguo la funzione che può anche ciclare all'infinito
return 0;
Ora dovrei dare in input la funzione h(x) (che calcola l'indice x per cui ho quella data istanza di g(x,n)) alla f di partenza e mostrare che ottengo una funzione che risolve il problema della terminazione.
$f(h(x))={ (0 if varphi_x(x)darr),(uarr if varphi_x(x)uarr):}$
Il problema è che non dovrebbe divergere mai altrimenti non mi riduco al problema della terminaizone. Qualcuno sa aiutarmi? Non riesco a venirne a capo da solo.
