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?
Riduzione di K complemento a TOT
-
- 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.
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.)
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.
![Razz :P](./images/smilies/icon_razz.gif)
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.)