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 $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:

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

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

Ejercicio 2

Sea $f:\mathbb {N} \rightarrow \mathbb {N}$ una función total tal que dado $x\in \mathbb {N}$, si $z$ es el menor número tal que $z\geq x$ y $\Phi _{z}$ computa la función identidad, $f(x)=z$. Decida y demuestre si $f$ 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. ${\mathcal {S}}=\left\lbrace x:{\text{para todo }}y{\text{, si }}\Phi _{x}^{(1)}(y)\downarrow {\text{, entonces }}\Phi _{x}^{(1)}(y){\text{ es un número primo}}\right\rbrace$

b. ${\mathcal {T}}=\left\lbrace x:{\text{para todo }}z{\text{ }}\Phi _{x}^{(1)}(z)\downarrow {\text{ y }}\Phi _{x}^{(1)}(z)>5\right\rbrace$

Ejercicio 4

Considere la clase de conjuntos ${\mathcal {R}}_{n}$ definida como:

${\mathcal {R}}_{n}=\left\lbrace x:\Phi _{x}^{(1)}(n)\uparrow \right\rbrace .$

a. Decida y demuestre si los conjuntos ${\mathcal {R}}_{n}$ son computables, c.e. y/o co-c.e.

b. Decida y demuestre si ${\mathcal {R}}=\cup _{n=0}^{\infty }{\mathcal {R}}_{n}$ es computable, c.e. y/o co-c.e.