Domande su insiemi ricorsivi e r.e

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

MindFlyer
Domande fatte negli ultimi 5 minuti di una lezione:
Presa [math] : [math] -> [math] e l'insieme A : non vuoto, sottoinsieme di [math] :
- se A ricorsivo allora(?) f^-1(A) = { n appartenente a [math] | f(n) appartiene ad A} è ricorsivo?
- se A ricorsivo allora(?) f^-1(A) è r.e.?
- se A ricorsivo allora(?) f(A) è ricorsivo?
- se A ricorsivo allora(?) f(A) è r.e.?


Se non si fanno ipotesi su f, la risposta a ogni domanda è ovviamente "a volte sì, a volte no".
Vogliamo per esempio che f sia calcolabile?

Di solito su problemi di questo tipo preferisco non dare direttamente la risposta, perché sarebbe inutile. Prima scrivi una soluzione tua (o un approccio), e poi discutiamo su quello.
Rispondi

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