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

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

Comments

  • MindFlyerMindFlyer Posts: 436
    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.
  • andreRondoandreRondo Posts: 25
    Perfetto, ti ringrazio :)
Sign In or Register to comment.