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 (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 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 termina en algúna cantidad de pasos 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} : \phi_y(y) \text{ termina en x' pasos} \\ 0 \quad\text{ si existe } x : \phi_e(x) \gt y \wedge (\forall x')_{\leq x} : \phi_y(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, no en pasos.

Error al representar (función desconocida «\gt»): {\displaystyle \quad g(x_2) \gt y } pero 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 (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 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