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.