Recuperatorio de computabilidad Verano 2018 (DC)

De Cuba-Wiki

Ejercicio 1

Considere el predicado pitagórica: que dados e nos dice si es un cuadrado perfecto, por ejemplo:

demuestre que el predicado pitagórica(x,y) es primitivo recursivo.

Solución

Quiero ver que existe un tal que: y que lo puedo hallar de forma primitiva recursiva.

pitagórica

con el predicado: . Vemos que es primitivo recursivo por se composición de funciones primitivas recursivas.

ahora veamos la cota.

Sea cota

simplemente observemos que

tenemos que cota cumple con que z es a lo sumo cota por lo tanto el existencial está bien definido como primitivo recursivo.

Ejercicio 2

Considere la función devuelve el menor número que cumple que no es computable.

Solución [1]

La imagen de son programas que terminan cuando se los valua en su propio número de programa. Uno está tentado en hacer una reducción a pero esto no parece funcionar. [2]

Veamos, que otras cosas nos dice .

Si esto nos dice que y es el mínimo programa que termina en una cantidad de pasos mayor a . Pero entonces todos los programas menores a y o bien terminan en una cantidad menor o igual a de pasos o se indefinen.

La idea es decir que si 'g' fuera computable, me dan un número de programa 'y', entonces usando 'g' si para algún valor de 'x' tengo un Error al representar (función desconocida «\gt»): {\displaystyle g(x) = y_2 \gt y} entonces resolví HALT que sabemos que no es computable. Esto es porque por lo anterior, solo tengo que comprobar si algúna cantidad de pasos logra terminar y en caso contrario es que se indefine.

Escribamos eso, queremos un f que se comporte como HALT. Sea 'e' el número del programa que computa la función 'g', sea 'P' el programa:

Error al representar (error de sintaxis): {\displaystyle \text{A:} \quad Z_2 \leftarrow Z_2 + 1 \text{ // el cero no nos interesa} \\ \quad\quad Z_1 \leftarrow \phi_{e}(Z_2) \\ \quad\quad \text{ IF } Z_1 \leq X_1 \text{ GOTO A // buscamos un programa más grande que x1} \\ \text{C:}\quad \text{IF STP}(X_1, X_1, Z_2) = 1 \text{ GOTO T} \\ \quad\quad Z_2 \leftarrow Z_2 - 1 \\ \quad\quad\text{IF} Z_2 \neq 0 \text{ GOTO C } \\ \quad\quad Y \leftarrow 0 \\ \quad\quad\text{GOTO E} \\ \text{T:}\quad Y \leftarrow 1}

Para ser más claro:

Error al representar (función desconocida «\gt»): {\displaystyle \psi_p(y) = \begin{cases} 1 \quad\text{ si existe } x : \phi_e(x) \gt y \wedge (\exists x')_{\leq x} : y \text{ termina en x' pasos} \\ 0 \quad\text{ si existe } x : \phi_e(x) \gt y \wedge (\forall x')_{\leq x} : y \text{ no termina en x' pasos} \\ \uparrow \quad\text{ no existe } x: \phi_e(x) \gt y \end{cases}}

Pero si no termina en o menos pasos quiere decir que o bien termina en más cantidad de pasos o se indefine. Pero si termina en más pasos, no puede ser menor a pues este era el mínimo, esto es absurdo, así que debe indefinirse.

Por lo tanto re escribimos,

Error al representar (función desconocida «\gt»): {\displaystyle \psi_p(y) = \begin{cases} 1 \quad\text{ si existe } x : \phi_e(x) \gt y \wedge (\exists x')_{\leq x} : \phi_y(y) \text{ termina en x' pasos} \\ 0 \quad\text{ si existe } x : \phi_e \gt y \wedge \phi_y(y) \text{ se indefine} \\ \uparrow \quad\text{ no existe } x: \phi_e(x) \gt y \end{cases}}

Ahora solo queda ver que siempre existe un Error al representar (función desconocida «\gt»): {\displaystyle x:g(x)\gt y} .

Veamos que no tiene cota.

Sea y los pasos en que termina .

Sea Error al representar (función desconocida «\gt»): {\displaystyle x' \gt x_2 \gt x} los pasos en que termina . Esto está bien de suponer porque no hay una cota a la cantidad de pasos que puede tardar un programa en terminar.

entonces hay tres casos:

Error al representar (función desconocida «\lt»): {\displaystyle \quad g(x_2) \lt y } pero entonces pues hay un programa más chico que termina en más de pasos.

pero entonces termina en pasos.

Error al representar (función desconocida «\gt»): {\displaystyle \quad g(x_2) \gt y } entonces no era el máximo de la imagen.

Los tres casos terminan en absurdo y lo único que supusimos es que existe un máximo de la imagen de 'g'. Por lo tanto 'g' no tiene cota.

Es decir siempre va a existir un Error al representar (función desconocida «\gt»): {\displaystyle x : g(x) \gt y } y podemos volver a re, rescribir

Computamos HALT que sabemos que no es computable, por lo tanto 'g' no es computable.

Notas

[1] Este ejercicio no está corregido por docentes. Lo hice mal en el examen y luego en la consulta me tiraron la idea. Lo hice mientras escribía esta wiki.

[2] Esto es lo que hice en el examen. Claramente mal. Es facil: identidad no es, aunque es claramente un subconjunto. Que no es exactamente se ve facil. Agarramos cualquier programa que nos devuelva y le agregamos instrucciones que no hacen nada. Esa 'transformación' saca al programa de la imagen de 'g' pero sigue estando en . Sin embargo esta 'transformación' no es la única, no podriamos obtener todos los programas de . Pueden divertirse un rato pensado transformaciones, yo no llegué a nada.

Ejercicio 3

Decida y justifique si los siguientes conjuntos son p.r, c.e., co-c.e o computables:

Error al representar (función desconocida «\gt»): {\displaystyle C_1 = {x \in \mathbb{N} : \text{para todo } y \in \mathbb{N}, \phi_x^{(1)}(2y)\downarrow} \text{ y } \phi_x^{(1)}(2y) \gt 5 } Error al representar (función desconocida «\gt»): {\displaystyle C_2 = {x \in \mathbb{N} : \text{para todo } y \in \mathbb{N}, \phi_x^{(1)}(2y)\uparrow} \text{ o } \phi_x^{(1)}(2y) \gt 5 }

Solución

Veamos el complemento de

como voy a mirar la desigualdad.

Veamos que es un conjunto de índices.

Sea por lo tanto

Esto es equivalente a decir que \overline{C_2} es un conjunto de índices (ej. 9 práctica 5). Además es una función que está en el conjunto mientras que es una funcíon que no, entonces \overline{C_2} no es trivial.

Por el Teorema de Rice, \overline{C_2} no es computable.

Veamos si es c.e. Para esto debe existir una función parcial computable que decida la pertenencia a .

Sea

con y

pero esto es una minimización no acotada de un predicado primitivo recursivo. Por lo tanto es parcial computable y decide la pertenencia a implica que es c.e.

Pero no es computable no es co.ce.

Resumiendo:

no computable. co.ce. no ce.

Parece que este conjunto es reducible a Tot.

Quiero una f tal que es total sii Error al representar (función desconocida «\gt»): {\displaystyle \phi_{f(x)}(2y)\downarrow \wedge \phi_{f(x)}(2y)\gt 5 }

Sea

Como g es parcial computable, existe e :

por teo del parámetro existe una función primitiva recursiva S, tal que:

Veamos que

Error al representar (error de sintaxis): {\displaystyle x\in\text{Tot} \implies \phi_x(y) \downarrow \forall y \in \mathbb{N} \implies \phi_x(2y) \downarrow \implies g(x, y) = 6 = \phi_e(y) \implies \phi_{f(x)}(y) \\ \implies \phi_{f(x)}(2y) = 6 \implies f(x) \in C_1 }

como f es p.r. .

no es c.e, ni co.ce, ni computable ni p.r

Ejercicio 4

Decida y justifique si existe un e tal que para todo x,

Solución

Sea

es una función parcial computable, entonces por el teorema del parámetro, éxiste un número de programa e tal que:

que cumple:

El enunciado es verdadero