Edición de «Parcial de Computabilidad Verano 2016 (LyC)»

{{Back|Lógica y Computabilidad}}

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 <math>ordenar : \mathbb{N} \to \mathbb{N}</math> la función que ordena una lista de números naturales de menor a mayor. Más explícitamente, <math>ordenar(0) = 0</math> y dado un numero natural <math>x > 0</math>, 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 <math>ordenar</math> es primitiva recursiva.

== Ejercicio 2 ==
Sea <math>n \in \mathbb{N}</math> un número natural fijo. Demostrar que la siguiente función es parcial computable:

<math>
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}
</math>

donde <math>ordenar</math> 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.''' <math>
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}
</math>

'''b.''' <math>
g(x) = \begin{cases} 1 & \text{si existe } y \geq x \,|\, \Phi_y^{(1)}(3x+5) = 8 \\
0 & \text{en caso contrario} \end{cases}
</math>

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

'''a.''' Si <math>G</math> es c.e. entonces <math>G</math> es computable.

'''b.''' Si <math>L</math> es c.e. entonces <math>L</math> es computable.