Riducibilità

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

Levi_92
Tra le domande del Turini ho trovato questa :
Dimostrare che se A è riducibile a B e B è r.e. allora A è r.e.
Ho cercato Nel libro ma viene data per vera senza alcuna dimostrazione .. qualcuno potrebbe aiutarmi a ricostruirla ?

MindFlyer
Sì, ti posso aiutare a ricostruirla, e per questo t'invito a scrivere un approccio di dimostrazione da cui poi possiamo partire.

Levi_92
Io avrei risposto così:
se un insieme è riducibile ad un altro vuol dire che posso riportare il comportamento dell'insieme più piccolo nell'insieme più grande, quindi:
se B è r.e. e A è riducibile a B vuol dire che A o è r.e. o ricorsivo e quindi se l'insieme è ricorsivo (e ha funzione caratteristica), tutto quello che appartiene ad A lo ributto in B e tutto quello che non appartiene ad A lo metto in tutto ciò che fa divergere B. Così ho riportato un insieme ricorsivo ad r.e.
Se A invece è r.e. allora tutto ciò che appartiene ad A e quindi ha fatto terminare la funzione parziale ricorsiva lo ributto in B perché come fa terminare A, fa terminare B visto che si può ridurre; mentre tutto quello che fa divergere A lo metto in tutto quello che fa divergere B e così un insieme r.e. a r.e.

MindFlyer
Cerco di evidenziare qualcuna delle pecche di questa cosa. Devo dire però che il discorso generale che fai ha ben poco senso, e mi posso solo limitare a isolare e analizzare qualche frammento. Sul senso generale non mi pronuncio perché non c'è nulla. Penso che tu debba ripassare molto bene le definizioni di tutto (prima di cercare di fare gli esercizi).


Levi_92 wrote: »
l'insieme più piccolo nell'insieme più grande

Non parlare di insiemi piccoli e grandi, perché non è detto che A sia più grande di B o viceversa. Per esempio, [math] e [math] sono due insiemi r.e., e ciascuno è riducibile all'altro.


Levi_92 wrote: »
A o è r.e. o ricorsivo

Se è ricorsivo, è anche r.e.; quindi non si capisce perché distinguere due casi uno dei quali include l'altro.


Levi_92 wrote: »
l'insieme è ricorsivo (e ha funzione caratteristica)

Tutti gli insiemi (ricorsivi e non) hanno funzione caratteristica. Anche qui, non si capisce il senso di questa affermazione.


Levi_92 wrote: »
se B è r.e. e A è riducibile a B vuol dire che A o è r.e. o ricorsivo

Questo è ciò che devi dimostrare... Sembra invece che tu lo prenda come punto di partenza!


Levi_92 wrote: »
ciò che fa divergere B

B è un insieme, e niente lo fa divergere. Quel che diverge è una qualche funzione calcolabile che termina solo su B, la quale esiste perché B è r.e. per definizione.


Levi_92 wrote: »
Così ho riportato un insieme ricorsivo ad r.e.

Questo non ha senso. Di nuovo, un insieme ricorsivo è già r.e.; cosa significa "riportarlo" ad r.e.?


Levi_92 wrote: »
Se A invece è r.e.

Il contrario di "ricorsivo" non è "r.e.", ma è "non ricorsivo". Questo caso manca completamente dall'analisi.


Levi_92 wrote: »
tutto quello che fa divergere A lo metto in tutto quello che fa divergere B

Non necessariamente ciò che non è in A deve andare in tutto ciò che non è in B. Tornando all'esempio sopra, la riduzione da [math] a [math] non manda mica ciò che non è in [math], ovvero [math], in tutto ciò che non è in [math], ovvero [math].


Levi_92 wrote: »
e così un insieme r.e. a r.e.

Non capisco il senso di questa frase a livello di analisi logica. Qual è il verbo?

Ymir
Facci sapere se quando hai ripassato non ti torna lo stesso! Non so che libro hai guardato, ma la spiegazione la trovi anche nelle dispense.
Rispondi

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