Ejercicio 1. Demostrar que las funciones y se encuentran en toda clase PRC.
Ejercicio 2. Decidir si el siguiente conjunto es i) p.r., ii) c.e. y co-c.e., iii) sólo c.e., iv) sólo co-c.e., v) ni c.e. ni co-c.e.
Ejercicio 3. Decidir si cada una de las siguientes afirmaciones es verdadera o falsa y justificar.
i) Si y son dos conjuntos no computables tal que , entonces existe no computable tal que .
ii) Si es un conjunto de índices no trivial, entonces existe un conjunto de índices no trivial tal que .
Ejercicio 4. Decidir si el siguiente conjunto es i) p.r., ii) c.e. y co-c.e., iii) sólo c.e., iv) sólo co-c.e., v) ni c.e. ni co-c.e.
|