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 $f:\mathbb {N} \to \mathbb {N}$ la función que calcula el producto de Kronecker entre dos listas. Es decir, $f(x,y)$ devuelve una lista de listas $L$ tal que $L[i][j]=x[j]y[i]$. Por ejemplo:

$f([x_{1},x_{2},x_{3}],[y_{1},y_{2}])=[[x_{1}y_{1},x_{2}y_{1},x_{3}y_{1}],[x_{1}y_{2},x_{2}y_{2},x_{3}y_{2}]].$

Decida si $f$ 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:

Error al representar (SVG o PNG como alternativa (MathML puede ser habilitado mediante plugin de navegador): respuesta no válida («Math extension cannot connect to Restbase.») del servidor «https://en.wikipedia.org/api/rest_v1/»:): {\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: $\Phi _{z}^{(1)}(y)=\Phi _{x}^{(1)}(y)+1$ quiere decir que el programa con número $z$ se indefine cuando el programa con número $x$ se indefine, y que devuelve el siguiente de lo que devolvió el programa con número $x$ cuando este último termina.

b. Existe un programa $P$ tal que:

$\Psi _{P}^{(2)}(x,y)={\begin{cases}x+y+\#P&x\leq y\\\uparrow &{\text{otro caso.}}\end{cases}}$

Ejercicio 3

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

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

${\mathcal {S}}=\left\lbrace \langle x,y\rangle :\Phi _{x}^{(1)}(y)\downarrow y\operatorname {STP} \left(y,x,\Phi _{x}^{(1)}(y){\dot {-}}1\right)\right\rbrace$

Ayuda: Piense cuáles son los elementos de ${\mathcal {S}}$.

Aclaración: Para todo $y$, $\operatorname {STP} (y,x,0)=1$ sii $x=0$.

Ejercicio 4

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

${\mathcal {T}}=\left\lbrace x:\Phi _{x}^{(1)}(y)\uparrow {\text{ para todo }}y\right\rbrace$