Edición de «Parcial de computabilidad Verano 2017 (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.

== Ejercicio 1 ==
Sea <math>f : \mathbb{N} \to \mathbb{N}</math> la función que calcula el producto de Kronecker entre dos listas. Es decir, <math>f(x,y)</math> devuelve una lista de listas <math>L</math> tal que <math>L[i][j] = x[j]y[i]</math>. Por ejemplo:

<math>f([x_1,x_2,x_3], [y_1,y_2]) = [[x_1y_1, x_2y_1, x_3y_1], [x_1y_2, x_2y_2, x_3y_2]].</math>

Decida si <math>f</math> es p. r. y justifique su respuesta.

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

'''a.''' La siguiente función es computable:

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

Aclaración: <math>\Phi^{(1)}_z (y) = \Phi^{(1)}_x(y) + 1</math> quiere decir que el programa con número <math>z</math> se indefine cuando el programa con número <math>x</math> se indefine, y que devuelve el siguiente de lo que devolvió el programa con número <math>x</math> cuando este último termina.

'''b.''' Existe un programa <math>P</math> tal que:

<math> \Psi^{(2)}_P(x,y) = \begin{cases}
    x + y + \#P & x \leq y \\
    \uparrow & \text{otro caso.} \end{cases} </math>

== Ejercicio 3 ==

'''a.''' Demuestre que si un programa de número <math>x</math> termina con entrada <math>y</math> entonces
vale que <math>\Phi^{(1)}_x(y) \leq t</math>, para todo <math>t</math> tal que <math>\operatorname{STP}(y, x, t)</math>.

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

<math>\mathcal{S} = \left\lbrace \langle x,y \rangle : \Phi^{(1)}_x(y) \downarrow y \operatorname{STP} \left( y, x, \Phi^{(1)}_x(y) \dot{-} 1 \right) \right\rbrace</math>

Ayuda: Piense cuáles son los elementos de <math>\mathcal{S}</math>.

Aclaración: Para todo <math>y</math>, <math>\operatorname{STP}(y, x, 0) = 0</math>.

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

<math>\mathcal{T} = \left\lbrace x : \Phi^{(1)}_x(y) \uparrow \text{ para todo } y \right\rbrace</math>