decidibilità di un insieme

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

Da facebook, domanda di un orale:
Dire se [math] è ricorsivo, ricorsivamente enumerabile o non ricorsivamente enumerabile.

Ho provato a ridurre K ad A, ridurre lui a K, anche a ridurre il suo complementare a K ma invano. Intuitivamente penso che sia non ricorsivo (forse anche non ricorsivamente enumerabile), ma non riesco a dimostrarlo formalmente.

Sono riuscito a dimostrarlo nel problema "giocattolo" in cui l'uguaglianza fra due funzioni non tiene conto di quando una delle due diverge, ma così com'è non mi riesce proprio. Qualcuno mi dà una dritta?

MindFlyer
Okay. Dico subito che l'esercizio è molto difficile, e secondo me ha poco senso aspettarsi che uno studente lo risolva all'esame (forse negli anni '50 aveva senso, ma coi tempi che corrono...). Io so dimostrare che [math] non è ricorsivo con un metodo completamente ad hoc, ma al momento non so dire se è ricorsivamente enumerabile (fermo restando che probabilmente non lo è, ma il problema è dimostrarlo). Quindi la mia ipotesi è che Degano l'abbia posto come "domanda molto aperta" con lo scopo di vedere come il candidato ragionava. Non sono nemmeno sicuro che Degano lo sapesse risolvere... Ricordiamo che dall'orale di Degano si può uscire con 30 e lode anche senza risolvere esattamente tutti i problemi che pone, ma mostrando di aver capito la teoria e saperla applicare.


Detto questo, vi propongo due esercizi che vanno nella direzione della mostruosità qui sopra, ma sono più facili e decisamente abbordabili. Fatti questi, posso mettervi sulla strada giusta per risolvere almeno in parte il problema originale.

Esercizio 1. Dimostrare che [math] non è tutto [math] e non è vuoto.
[La prima parte è quasi banale; la seconda è un'immediata applicazione di un teorema visto nel corso.]

Esercizio 2. Dimostrare che esiste una numerazione ammissibile delle funzioni calcolabili che rende [math] non ricorsivamente enumerabile.
[Ricordo che una numerazione ammissibile delle macchine di Turing è una indicizzazione che sia ottenibile in modo calcolabile da quella standard [math], e viceversa.]

ivansarno
dato B il sottoinsieme di A con soli indici di funzioni totali, B complemento si riduce a K0, se B complemento non è ricorsivo B è CoRE ed A nonRE, ma non trovo niente per dimostrare che non è ricorsivo :(

dato B il sottoinsieme di A con soli indici di funzioni totali, B complemento si riduce a K0, se B complemento non è ricorsivo B è CoRE ed A nonRE, ma non trovo niente per dimostrare che non è ricorsivo :(

MindFlyer
Veramente non colgo il senso di questo. :(
Facciamo prima gli esercizi 1 e 2 che ho posto io (che sono fattibili!). Poi vediamo come fare quello di Degano.

Lucio Messina
@MindFlyer: c'è un teorema che abbiamo dimostrato a lezione che permette di classificare gli insiemi in base alla classificazione del loro complemento. Non me lo ricordo bene perché ho fatto l'esame un anno fa, sono un po' arrugginito e non ho la dispensa sotto mano.

Comunque: dimostrare che A non è tutto N: sia f(x) = 0 per ogni x. È intuitivamente calcolabile, quindi ha un indice p. Sia g(x) = 1 per ogni x. È intuitivamente calcolabile ed è diversa da f, quindi ha un indice q diverso da p.
Se A fosse tutto N, tutte le funzioni calcolerebbero la stessa cosa (perché ϕ0 = ϕ1 = ϕ2 ...) ma io ho trovato due funzioni che calcolano due cose diverse (ϕp e ϕq). quindi almeno uno fra p e q non appartiene ad A, e A non è tutto N.

MindFlyer
Intanto un aggiornamento: ho confermato che la r.e. di quell'insieme dipende dalla particolare numerazione delle funzioni calcolabili. Quindi, riassumendo: l'insieme non è ricorsivo (qualunque sia la numerazione), ed è r.e. o non r.e. a seconda della numerazione. Il tutto si può dimostrare con gli strumenti del corso, quindi con un po' di pazienza arriveremo a dimostrarlo in questo thread, spero...


Tornando a bomba...
c'è un teorema che abbiamo dimostrato a lezione che permette di classificare gli insiemi in base alla classificazione del loro complemento.
Io avevo in mente un altro teorema. Pensa a come poter "parafrasare" la definizione di [math] in termini di... (e se dico altre due paroline capisci subito :) ).
Comunque: dimostrare che A non è tutto N: sia f(x) = 0 per ogni x. È intuitivamente calcolabile, quindi ha un indice p. Sia g(x) = 1 per ogni x. È intuitivamente calcolabile ed è diversa da f, quindi ha un indice q diverso da p.
Se A fosse tutto N, tutte le funzioni calcolerebbero la stessa cosa (perché ϕ0 = ϕ1 = ϕ2 ...) ma io ho trovato due funzioni che calcolano due cose diverse (ϕp e ϕq). quindi almeno uno fra p e q non appartiene ad A, e A non è tutto N.
Ottimo questo. Cioè, quasi ottimo: nota che [math] e [math] potrebbero essere entrambi in [math] pur essendo [math] e [math] funzioni diverse. Ma la sostanza è giusta.

Lucio Messina
Vero, non ci avevo pensato. Comunque rimane il fatto che se A fosse tutto N, tutte le funzioni calcolerebbero la stessa cosa. Sia quindi n il minore fra p e q e m il maggiore. φn è diverso da φm.
Se A fosse tutto N, allora tutti i numeri compresi fra n ed m apparterrebbero ad A. Quindi dovrebbe essere
φn = φn+1 = φn+2 = ... = φm
che è assurdo perché φn diverso da φm.

MindFlyer
Per dire che A non è vuoto, pensa al fatto che x+1 è una trasformazione sugli indici... Quali teoremi conosci sulle funzioni che trasformano gli indici?

Niente? Punti fissi...?

GaspareFerraro
Dal teorema di ricorsione sappiamo che per la funzione [math] [math] tale che [math]
( quindi [math] tale che [math] )
Da questo si capisce che l'insieme non è vuoto, inoltre sempre per un risultato scritto nelle dispense (padding lemma) i punti fissi hanno cardinalità di [math].

MindFlyer
Bene!
La seconda parte non era richiesta, ed è effettivamente contenuta nelle dispense (Proprietà 1.9.15). Nota che il padding lemma non va applicato direttamente al punto fisso x (perché non è detto che i successori dei suoi indici omologhi siano anch'essi omologhi), bensì ad h(x) e grazie all'iniettività di d, dove h e d sono definite in 1.9.15 e 1.9.14.


L'altra metà dell'esercizio 1 era già stata risolta da @Lucio Messina, quindi non ci resta che passare all'esercizio 2, che è più interessante.
Rispondi

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