Parcial 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, apellido y número de orden.

Ejercicio 1[editar]

Sea la función que calcula el producto de Kronecker entre dos listas. Es decir, devuelve una lista de listas tal que . Por ejemplo:

Decida si es p. r. y justifique su respuesta.

Ejercicio 2[editar]

Diga si las siguientes afirmaciones son verdaderas o falsas. Justifique sus respuestas.

a. La siguiente función es computable:

Error al representar (función desconocida «\begin{cases}»): {\displaystyle f(x) = \begin{cases} 1 & \text{si existe $z$ tal que $\Phi^{(1)}_z (y) = \Phi^{(1)}_x(y) + 1$ para todo $y$} \\ 0 & \text{otro caso.} \end{cases} }

Aclaración: quiere decir que el programa con número se indefine cuando el programa con número se indefine, y que devuelve el siguiente de lo que devolvió el programa con número cuando este último termina.

b. Existe un programa tal que:

Ejercicio 3[editar]

a. Demuestre que si un programa de número termina con entrada entonces vale que , para todo tal que .

b. Decida si el siguiente conjunto es c.e., co-c.e. y/o computable:

Ayuda: Piense cuáles son los elementos de .

Aclaración: Para todo , .

Ejercicio 4[editar]

Decida si el siguiente conjunto es c.e., co-c.e. y/o computable: