Parcial de Computabilidad Verano 2016 (LyC)

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. El examen consta de 4 ejercicios de igual valor. Cada ejercicio sera calificado con A (aprobado), R (regular) o I (insuficiente), ocasionalmente con un signo — (menos). Para aprobar un parcial es necesario tener al menos dos ejercicios calificados con A o A—. Para promocionar es necesario tener al menos tres ejercicios calificados con A o A- en ambos parciales o sus correspondientes recuperatorios.

Ejercicio 1

Sea $ordenar:\mathbb {N} \to \mathbb {N}$ la función que ordena una lista de números naturales de menor a mayor. Más explícitamente, $ordenar(0)=0$ y dado un numero natural $x>0$, lo interpreta como una lista de números naturales sin ceros al final y devuelve la codificación de la lista que resulta de ordenar los elementos de la original de menor a mayor. Demostrar que la función $ordenar$ es primitiva recursiva.

Ejercicio 2

Sea $n\in \mathbb {N}$ un número natural fijo. Demostrar que la siguiente función es parcial computable:

$f(x)={\begin{cases}1&{\text{si existen }}x_{1},...x_{n}\,|\,\Phi _{x}^{(n)}(x_{1},...x_{n})\downarrow {\text{ y }}\Phi _{x}^{(n)}(x_{1},...x_{n})\neq ordenar([x_{1},...x_{n}])\\\uparrow &{\text{en caso contrario}}\end{cases}}$

donde $ordenar$ es la función del Ejercicio 1 y puede asumirse el resultado de ese ejercicio como válido.

Ejercicio 3

Decidir si las siguientes funciones son computables o no. Justificar la respuesta.

a. $f(x,y)={\begin{cases}1&{\text{si }}\Phi _{x}^{(1)}(y)=0{\text{ ó }}\Phi _{y}^{(1)}(0)=0\\0&{\text{en caso contrario}}\end{cases}}$

b. $g(x)={\begin{cases}1&{\text{si existe }}y\geq x\,|\,\Phi _{y}^{(1)}(3x+5)=8\\0&{\text{en caso contrario}}\end{cases}}$

Ejercicio 4

Sea $f:\mathbb {N} \to \mathbb {N}$ una función total, $G=\{\langle x,y\rangle :y=f(x)\}$ y $L=\{\langle x,y\rangle :y\leq f(x)\}$. Decidir si son verdaderas o falsas las siguientes afirmaciones. Justificar la respuesta.

a. Si $G$ es c.e. entonces $G$ es computable.

b. Si $L$ es c.e. entonces $L$ es computable.