Riduzione di K complemento a TOT

[InformateciBot]

Salve a tutti,
Rileggendo le dispense di Degano ho trovato ke si può eseguire la riduzione da K complemento a TOT(insieme di indici di macchine che calcolano funzioni totali), tuttavia non ne dà una dimostrazione.
Qualcuno di voi sa che riduzione usare?

[LorenzoBuonanno]

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.)