MindFlyer
Sì, è una tipica domanda da esame, quindi non ti rispondo in modo diretto perché è più utile pensarci prima un po'.
Scrivi un approccio di soluzione, poi se ti blocchi la sistemiamo insieme.
goblin92
Avevo pensato di definire una funzione
[math]\psi(x,y)che se
[math]x \in K= indefinita, altrimenti gli assegnavo un valore costante.
Ma penso che questo non sia possibile visto che se
[math]x \notin K ,allora la macchina non si arresta...
MindFlyer
Ok, allora facciamo così.
Dobbiamo fare una riduzione da
[math]\overline K a
[math]TOT, ovvero vogliamo una funzione calcolabile
[math]f (la riduzione) tale che, per ogni indice di funzione calcolabile
[math]n,
[math]n\in K \iff f(n)\notin TOT.
Dunque, se
[math]\varphi_n(n) si arresta in un numero finito di passi, vogliamo produrre una funzione
[math]\varphi_{f(n)} che non è totale.
Invece, se
[math]\varphi_n(n) non si arresta in un numero finito di passi, vogliamo produrre una funzione
[math]\varphi_{f(n)} che è totale.
Impostando le cose così ce la possiamo fare abbastanza facilmente.
Cosa deve fare
[math]f? Si prende in input un
[math]n, e costruisce una funzione calcolabile (immaginala come un programma)
[math]\varphi_{f(n)} che farà questo: prende un input
[math]m, e simula
[math]\varphi_n(n) per
[math]m passi. In base a questa simulazione, calcolerà un certo
[math]\varphi_{f(n)}(m)...
In che modo? Qui ti lascio il compito di concludere.
Tutto tace, quindi concludo io. Se hai dubbi sulla soluzione, chiedi.
Se
[math]\varphi_n(n) termina in meno di
[math]m passi,
[math]\varphi_{f(n)}(m) cicla all'infinito. Altrimenti,
[math]\varphi_{f(n)}(m) termina con un output qualsiasi.
Quindi, se
[math]n\in K, prima o poi
[math]\varphi_n(n) termina, e
[math]\varphi_{f(n)}(m) comincia ad essere indefinita da un certo
[math]m poi. Dunque
[math]f(n)\notin TOT. Se invece
[math]n\notin K,
[math]\varphi_n(n) non termina mai, e
[math]\varphi_{f(n)}(m) è definita per ogni
[math]m. Dunque
[math]f(n)\in TOT.
cgiorgia_93
vedevo nelle dispense del turini che lui faceva una riduzione di K¯(segnato) a TOT¯(segnato)..ma cosi facendo non dimostro che TOT è r.e. giusto ?
MindFlyer
Così facendo dimostri che
[math]\overline{TOT} non è r.e., e questo di per sé non implica nulla sulla ricorsiva enumerabilità di
[math]TOT.
(Di solito il teorema che si usa per dimostrare in modo indiretto la non ricorsiva enumerabilità è quello che dice che se un insieme e il suo complementare sono r.e., allora sono ricorsivi. Dunque, se
[math]A è non ricorsivo e
[math]\overline{A} è r.e., allora
[math]A non è r.e. Nel caso di
[math]TOT il teorema non si applica, perché sia
[math]TOT che il complementare non sono r.e.)