Edición de «Recuperatorio 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 y apellido.

== Ejercicio 1 ==

Decimos que un programa {{math|P}} es ''simple'' si todos los saltos condicionales son hacia adelante (es decir, hacia una línea de programa posterior a la del salto en cuestión). 

'''a.''' Decida y demuestre si la siguiente función es primitiva recursiva:

<math>
 f(x)=\begin{cases}
  1 & \text{si el programa de número }x\text{ es simple} \\
  0 & \text{si no.}
 \end{cases}
</math>

'''b.''' Decida y demuestre si es computable la función <math>g(x)=f(x) HALT(x,x)</math> con <math>f</math> la función del ítem anterior.

== Ejercicio 2 ==

Sea <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> una función total tal que dado <math>x \in \mathbb{N}</math>, si <math>z</math> es el menor número tal que <math>z\geq x</math> y <math>\Phi_z</math> computa la función identidad, <math>f(x)=z</math>. Decida y demuestre si <math>f</math> es computable o no.

== Ejercicio 3 ==

Para cada uno de los siguientes conjuntos, decida y demuestre si es c.e., co-c.e. y/o computable.

'''a.''' <math>\mathcal{S} = \left\lbrace x : \text{para todo }y\text{, si }\Phi^{(1)}_x(y) \downarrow\text{, entonces }\Phi^{(1)}_x(y)\text{ es un número primo} \right\rbrace</math>

'''b.''' <math>\mathcal{T}=\left\lbrace x :\text{para todo }z\text{ }\Phi_{x}^{(1)}(z)\downarrow\text{ y }\Phi_{x}^{(1)}(z) > 5 \right\rbrace</math>

== Ejercicio 4 ==
Considere la clase de conjuntos <math>\mathcal{R}_n</math> definida como:

<math>\mathcal{R}_n=\left\lbrace x: \Phi^{(1)}_x(n)\uparrow \right\rbrace.</math>

'''a.''' Decida y demuestre si los conjuntos <math>\mathcal{R}_n</math> son computables, c.e. y/o co-c.e.

'''b.''' Decida y demuestre si <math>\mathcal{R}=\cup_{n=0}^\infty \mathcal{R}_n</math> es computable, c.e. y/o co-c.e.