Recuperatorio de computabilidad Verano 2018 (DC)
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