Pagina 1 di 1

Domande su insiemi ricorsivi e r.e

Inviato: 23/05/2017, 10:13
da InformateciBot
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.