Riduzione di K complemento a TOT

Rispondi
Avatar utente
InformateciBot
Messaggi: 314
Iscritto il: 30/09/2018, 16:33

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
Messaggi: 29
Iscritto il: 10/02/2019, 23:23

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]che se [math], altrimenti gli assegnavo un valore costante.
Ma penso che questo non sia possibile visto che se [math],allora la macchina non si arresta...

MindFlyer
Ok, allora facciamo così.

Dobbiamo fare una riduzione da [math] a [math], ovvero vogliamo una funzione calcolabile [math] (la riduzione) tale che, per ogni indice di funzione calcolabile [math],

[math].

Dunque, se [math] si arresta in un numero finito di passi, vogliamo produrre una funzione [math] che non è totale.
Invece, se [math] non si arresta in un numero finito di passi, vogliamo produrre una funzione [math] che è totale.

Impostando le cose così ce la possiamo fare abbastanza facilmente.
Cosa deve fare [math]? Si prende in input un [math], e costruisce una funzione calcolabile (immaginala come un programma) [math] che farà questo: prende un input [math], e simula [math] per [math] passi. In base a questa simulazione, calcolerà un certo [math]...

In che modo? Qui ti lascio il compito di concludere. :P

Tutto tace, quindi concludo io. Se hai dubbi sulla soluzione, chiedi.

Se [math] termina in meno di [math] passi, [math] cicla all'infinito. Altrimenti, [math] termina con un output qualsiasi.

Quindi, se [math], prima o poi [math] termina, e [math] comincia ad essere indefinita da un certo [math] poi. Dunque [math]. Se invece [math], [math] non termina mai, e [math] è definita per ogni [math]. Dunque [math].

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] non è r.e., e questo di per sé non implica nulla sulla ricorsiva enumerabilità di [math].

(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] è non ricorsivo e [math] è r.e., allora [math] non è r.e. Nel caso di [math] il teorema non si applica, perché sia [math] che il complementare non sono r.e.)
Rispondi

Torna a “[ECC] Elementi di calcolabili e complessità”