Fissata un'enumerazione delle funzioni calcolabili, e detta $ \varphi_x $ la funzione calcolabile di indice x, dimostrare o confutare che l'insieme
$ S=\{ (x,y) | \varphi_x \neq \varphi_y \} $
è semidecidibile.
Semidecidibilità
Supponiamo per assurdo che S sia ricorsivamente enumerabile o equivalentemente che il predicato Ps(x,y) definito come
Ps(x,y) <-> Fx è diversa da Fy
sia semicomputabile.
Allora dal teorema di enumerazione di Kleene esiste un numero z tale che
Ps(x,y) <-> Esiste k T2(z,x,y,k)
Dove Tn(z,x1,x2,...xn,k) è il predicato vero se e solo se k è una compuazione della macchina di turing il cui numero di godel è z quando l'input è x1,x2,...xn.
(Tn è un ben conosciuto predicato computabile).
Consideriamo il predicato NOT Esiste k T1(z,z,k)
Per ogni macchina di turing z creiamo una nuova macchina di turing z1 il cui numero di godel è f(z) definita nel seguente modo:
z1 simula z con input z.
Se z termina restituisce 1.
f(z) è certamente ricorsiva.
Sia g(z) la funzione che calcola l'indice della funzione ricorsiva corrispondente a f(z) (l'enumerazione delle funzioni può essere per esempio definita come il numero di godel della macchina di turing equivalente a quella funzione, e g(z) restituirà gn(z1)).
g(z) è certamente ricorsiva.
Sia r l'indice della funzione ricorsiva definita come f(x)=1 per ogni x.
Si ha
NOT Esiste k T1(z,z,k) <-> Fr è diversa da F(g(z)) (con F(g(z)) intendo la funzione parzialmente ricorsiva il cui indice è g(z) )
(infatti se z con input z non halta allora anche f(z) non halta ed è pertanto diversa da 1.Not Esiste k T1(z,z,k)
viceversa, se f(z) è uguale a 1 allora f(z) halta e così halta z con input z)
Continuando la catena di implicazioni si ha
NOT Esiste k T1(z,z,k) <-> Fr è diversa da F(g(z))
<-> Ps(r,g(z)) <-> Esiste k T2(z,r,g(z),k)
Così { z | NOT Esiste k T1(z,z,k) } è il dominio della funzione parzialmente computabile min k Ct2(z,k)=0
dove con Ct2(z,k) si intende la funzione caratteristica del predicato computabile T2(z,r,g(z),k).
E per definizione di predicato semicomputabile
NOT Esiste k T1(z,z,k) è semicomputabile
Ma dal teorema di enumerazione di Kleene c'è un numero z0 tale che
NOT Esiste k T1(z,z,k) <-> Esiste k T1(z0,z,y)
Che per z=z0 equivale a
NOT Esiste k T1(z0,z0,k) <-> Esiste k T1(z0,z0,y)
Assurdo.
Ciò conclude la dimostrazione.
Ps(x,y) <-> Fx è diversa da Fy
sia semicomputabile.
Allora dal teorema di enumerazione di Kleene esiste un numero z tale che
Ps(x,y) <-> Esiste k T2(z,x,y,k)
Dove Tn(z,x1,x2,...xn,k) è il predicato vero se e solo se k è una compuazione della macchina di turing il cui numero di godel è z quando l'input è x1,x2,...xn.
(Tn è un ben conosciuto predicato computabile).
Consideriamo il predicato NOT Esiste k T1(z,z,k)
Per ogni macchina di turing z creiamo una nuova macchina di turing z1 il cui numero di godel è f(z) definita nel seguente modo:
z1 simula z con input z.
Se z termina restituisce 1.
f(z) è certamente ricorsiva.
Sia g(z) la funzione che calcola l'indice della funzione ricorsiva corrispondente a f(z) (l'enumerazione delle funzioni può essere per esempio definita come il numero di godel della macchina di turing equivalente a quella funzione, e g(z) restituirà gn(z1)).
g(z) è certamente ricorsiva.
Sia r l'indice della funzione ricorsiva definita come f(x)=1 per ogni x.
Si ha
NOT Esiste k T1(z,z,k) <-> Fr è diversa da F(g(z)) (con F(g(z)) intendo la funzione parzialmente ricorsiva il cui indice è g(z) )
(infatti se z con input z non halta allora anche f(z) non halta ed è pertanto diversa da 1.Not Esiste k T1(z,z,k)
viceversa, se f(z) è uguale a 1 allora f(z) halta e così halta z con input z)
Continuando la catena di implicazioni si ha
NOT Esiste k T1(z,z,k) <-> Fr è diversa da F(g(z))
<-> Ps(r,g(z)) <-> Esiste k T2(z,r,g(z),k)
Così { z | NOT Esiste k T1(z,z,k) } è il dominio della funzione parzialmente computabile min k Ct2(z,k)=0
dove con Ct2(z,k) si intende la funzione caratteristica del predicato computabile T2(z,r,g(z),k).
E per definizione di predicato semicomputabile
NOT Esiste k T1(z,z,k) è semicomputabile
Ma dal teorema di enumerazione di Kleene c'è un numero z0 tale che
NOT Esiste k T1(z,z,k) <-> Esiste k T1(z0,z,y)
Che per z=z0 equivale a
NOT Esiste k T1(z0,z0,k) <-> Esiste k T1(z0,z0,y)
Assurdo.
Ciò conclude la dimostrazione.
Vorrei aggiungere alcune considerazioni.
MindFlyer parlava di "funzioni calcolabili".
Ora con questo termine alcuni intendono le "funzioni totalmente calcolabili" altri quelle "parzialmente calcolabili".
Tecnicamente si dovrebbe usare la prima definizione.
Anche perchè se si parlasse di funzioni TOTALI e calcolabili allora quel problema sarebbe semidecidibile nell'ipotesi che esista una enumerazione delle funzioni totalmente calcolabili.
Il problema è che tale enumerazione non esiste.
Supponiamo infatti che esista una enumerazione effettiva F0, F1, F2...
di tutte le funzioni totali e calcolabili.
Formalmente fissata l'enumerazione effettiva standard di tutte le funzioni calcolabili (non necessariamente totali) E0,E1,E2...
stiamo supponendo che esista una funzione calcolabile totale g(i) tale che Eg(i)=Fi.
Consideriamo la funzione f(i)=Fi(i)+1.
f è calcolabile e totale.
Infatti f(i)=Eg(i)+1.
Pertanto f appartiene a tale enumerazione e allora esiste j tale che f=Fj.
f(j)=Fj(j)+1
ossia
f(j)=f(j)+1
Assurdo.
MindFlyer parlava di "funzioni calcolabili".
Ora con questo termine alcuni intendono le "funzioni totalmente calcolabili" altri quelle "parzialmente calcolabili".
Tecnicamente si dovrebbe usare la prima definizione.
Anche perchè se si parlasse di funzioni TOTALI e calcolabili allora quel problema sarebbe semidecidibile nell'ipotesi che esista una enumerazione delle funzioni totalmente calcolabili.
Il problema è che tale enumerazione non esiste.
Supponiamo infatti che esista una enumerazione effettiva F0, F1, F2...
di tutte le funzioni totali e calcolabili.
Formalmente fissata l'enumerazione effettiva standard di tutte le funzioni calcolabili (non necessariamente totali) E0,E1,E2...
stiamo supponendo che esista una funzione calcolabile totale g(i) tale che Eg(i)=Fi.
Consideriamo la funzione f(i)=Fi(i)+1.
f è calcolabile e totale.
Infatti f(i)=Eg(i)+1.
Pertanto f appartiene a tale enumerazione e allora esiste j tale che f=Fj.
f(j)=Fj(j)+1
ossia
f(j)=f(j)+1
Assurdo.