Recuperatorio de computabilidad Verano 2017 (LyC)

De Cuba-Wiki
Saltar a: navegación, buscar

El examen es a libro abierto y se puede suponer demostrado lo dado en las clases y los ejercicios de las guías colocando referencias claras. Entregar cada ejercicio en hojas separadas. En cada hoja debe figurar nombre y apellido.

Ejercicio 1[editar]

Decimos que un programa es simple si todos los saltos condicionales son hacia adelante (es decir, hacia una línea de programa posterior a la del salto en cuestión).

a. Decida y demuestre si la siguiente función es primitiva recursiva:

b. Decida y demuestre si es computable la función con la función del ítem anterior.

Ejercicio 2[editar]

Sea una función total tal que dado , si es el menor número tal que y computa la función identidad, . Decida y demuestre si es computable o no.

Ejercicio 3[editar]

Para cada uno de los siguientes conjuntos, decida y demuestre si es c.e., co-c.e. y/o computable.

a.

b.

Ejercicio 4[editar]

Considere la clase de conjuntos definida como:

a. Decida y demuestre si los conjuntos son computables, c.e. y/o co-c.e.

b. Decida y demuestre si es computable, c.e. y/o co-c.e.