Differenza tra Ax e A i.i.r.f

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

andreRondo
Ciao a tutti, che differenza c'è tra l'insieme infinito di indici Ax di mdT che calcolano tutte la stessa funzione (Paddling lemma) e l'insieme A (nella definizione di i.i.r.f.) che è anch'esso un insieme di indici che calcolano tutte la stessa funzione?

Ho pensato alla cardinalità dei due insiemi.. Il primo è infinito. Il secondo non saprei, anche perchè grazie al teorema 1.10.19 e al teorema di Rice si può sapere se è r.e. oppure ricorsivo, e quindi la cardinalità in quei casi varia..

MindFlyer
Non fare una confusione assurda con le cardinalità. La cardinalità di tutti gli insiemi che hai citato è numerabile (tranne nel caso in cui sono vuoti).

La risposta alla domanda è presto data: l'insieme costruito nel padding lemma non è un insieme di indici che rispettano le funzioni. Nel padding lemma si generano alcuni indici che corrispondono alla stessa funzione (semplicemente perché si aggiungono operazioni inutili al "programma" della funzione). Ma ci sono invece molti altri indici che corrispondono alla stessa funzione ma non sono generati dal padding lemma. Perché dico questo? Perché l'insieme generato dal padding lemma è ricorsivo: tutti gli indici sono della forma "programma fissato (sempre lo stesso!) seguito da un numero qualunque di operazioni inutili". Altre varianti del padding lemma costruiscono altri insiemi, ma sono tutti ricorsivi. Però il teorema di Rice dice che l'insieme di indici di una funzione non è ricorsivo, e quindi dev'essercene qualcuno non generato dal padding lemma.
Rispondi

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