Pagina 1 di 1

Esercizio sul Padding Lemma

Inviato: 05/02/2017, 16:34
da InformateciBot
Tester
Ciao a tutti, leggendo le domande che il Degano ha fatto all'orale sono rimasto abbastanza perplesso sulla seguente:
"Sappiamo dal padding lemma che esiste una funzione che restituisce indici di macchine equivalenti. Ne può esistere una che li restituisce tutti?"
Credo che la risposta sia no, ma non riesco a dimostrare il perchè. Qualcuno ha idea di come si possa fare?

MindFlyer
Ovviamente una funzione che li restituisca tutti esiste, ma può essere calcolabile totale?

Tester
Avevo pensato ad una dimostrazione per assurdo. Poichè gli indici sono #N possiamo enumerarli, ovvero data x possiamo elencare gli indici di phi_x (ad esempio in ordine crescente): {x_0, x_1, ...} tale che phi_x = phi_i per ogni i. Sia quindi f una funzione calcolabile totale tc. dati x ed i restituisce l'i-esimo indice di phi_x. A questo punto dovrei far vedere che ci sono indici che non vengono generati da f, ma non mi vengono in mente quindi non so se questa sia la strada giusta...

MindFlyer
Rice ti dice niente?

Tester
Ok, forse ho capito. L'insieme di indici che stiamo generando credo sia un insieme di indici che rispettano le funzioni. Sia A_x l'insieme di indici di phi_x, presi i ed y qualunque, se i ∈ A_x e phi_i = phi_y allora, dato che A_x e' l'insieme di tutti gli indici di phi_x, anche y deve trovarsi in A_x (phi_x = phi_i = phi_y => y ∈ A_x). A_x non contiene però gli indici di tutte le funzioni calcolabili, contiene infatti solo quelli di phi_x, nè è vuoto perchè contiene x. Quindi per il teorema di Rice A_x non è ricorsivo. Giusto?

MindFlyer
Fin qui è giusto. Hai dimostrato che [math] non è ricorsivo, e quindi la sua funzione caratteristica non è calcolabile. Come si passa da qui a dire che non c'è una funzione calcolabile totale che genera tutti e soli gli elementi di [math]?

Tester
Pensavo ora di procedere per questa strada:
Sappiamo che [math] non è ricorsivo, dimostriamo, per assurdo, che se esistesse una funzione totale che genera elementi di [math] allora quest'ultimo sarebbe ricorsivo.
Sia [math] la funzione calcolabile totale che genera elementi di [math]. Poichè [math] ha #N indici credo si possa assumere che esista una [math] che generi indici in modo strettamente crescente. A questo punto per verificare se l'indice a appartiene ad [math] basta far generare a [math] indici. Nel caso in cui venga generato a, allora vuol dire che a ∈ [math]; invece nel caso in cui venga generato un indice maggiore di a allora vuol dire a ∉ [math]. Ma quindi abbiamo definito una funzione calcolabile totale, dato che [math] lo è, che decide a ∈ [math]. Quindi [math] è ricorsivo. Siamo giunti ad un assurdo.

MindFlyer
Ok, hai dimostrato che non esiste una funzione calcolabile totale e crescente che genera tutti e soli gli indici di [math] (devi dire tutti e soli, perché se ne genera solo qualcuno o genera anche qualcos'altro la dimostrazione non funziona).

Però questo passaggio non è giustificato:
Poichè [math] ha #N indici credo si possa assumere che esista una [math] che generi indici in modo strettamente crescente.
Per un insieme, essere l'immagine di una funzione calcolabile, totale, e crescente equivale ad essere ricorsivo. Invece, essere immagine di una funzione calcolabile totale (non necessariamente crescente) equivale ad essere ricorsivamente enumerabile. Quindi con Rice arrivi solo a dire che la tua funzione generatrice non può essere crescente (quando ho nominato Rice non ho pensato a questo, quindi ti ho messo un po' fuori strada... sarebbe stato giusto dire "Rice-Shapiro", che però non è parte del programma del corso).

Per risolvere l'esercizio completamente bisogna dimostrare che [math] non è ricorsivamente enumerabile, per esempio con una riduzione da [math]. E poi si dimostra il fatto che ho detto sopra, ovvero che se [math] non è ricorsivamente enumerabile, allora non esiste una funzione calcolabile totale che lo genera.

Tester
Grazie mille per la disponibilità, procederò per questa strada.