Pagina 1 di 1

Listing Theorem

Inviato: 26/12/2015, 22:17
da InformateciBot
(A r.e ) se e solo se ( A = {} or A = range(f) , f ricorsiva ).

potreste aiutarmi a capire la dimostrazione?

MindFlyer
Ok, assumiamo che usi la definizione secondo cui un insieme è ricorsivamente enumerabile se è il dominio di una funzione calcolabile.

Supponiamo che A sia ricorsivamente enumerabile, essendo il dominio di una funzione calcolabile g. Se A non è vuoto ed è finito, è banalmente l'immagine di una funzione ricorsiva. Se A è infinito, si può costruire una funzione ricorsiva (persino iniettiva) f di cui A è immagine, nel modo seguente. Diciamo che l'input di f è n. f simula il primo passo di g su input 1, poi il primo passo di g su input 2, poi il secondo passo di g su input 1, poi il primo passo di g su input 3, etc. In pratica è come se ci fosse una tabella infinita di coppie del tipo (input di g, passo), e f scorre tutte le diagonali (finite) della tabella. A un certo punto qualcuna di queste simulazioni termina. Siccome infinite simulazioni devono terminare, ci sarà un momento in cui f trova la (n+1)-esima terminazione, diciamo alla casella (i,p) della tabella. Quando questo succede, f restituisce i. E' chiaro che così l'immagine di f è esattamente l'insieme degli input su cui g termina, ovvero il dominio di g.

Supponiamo che A sia vuoto o l'immagine di una funzione f ricorsiva. Se è vuoto, è ovviamente ricorsivamente enumerabile (è il dominio di una funzione indefinita ovunque). Se A non è vuoto, vogliamo costruire una funzione g di cui A è il dominio. Sia n l'input di g. Allora g simula le esecuzioni di f sui vari input, seguendo le diagonali della tabella (input, passo), esattamente come sopra. Appena f restituisce il valore n, g termina. Altrimenti g continua l'esecuzione. In questo modo g termina se e solo se il suo input è nell'immagine di f.