Recuperatorio de computabilidad Verano 2018 (DC)

Ejercicio 1

Considere el predicado pitagórica: $\mathbb {N} ^{2}\rightarrow {0,1}$ que dados $x$ e $y$ nos dice si $x^{2}+y^{2}$ es un cuadrado perfecto, por ejemplo:

${\text{pitagórica}}(3,4)=1$

${\text{pitagórica}}(2,3)=0$

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

Solución

Quiero ver que existe un $z$ tal que: $x^{2}+y^{2}=z^{2}$ y que lo puedo hallar de forma primitiva recursiva.

pitagórica$(x,y)=(\exists z)_{\leq cota(x,y)}p(z,x,y)$

con $p$ el predicado: $p(t,x,y)=(t^{2}=x^{2}+y^{2})$. Vemos que $p$ es primitivo recursivo por se composición de funciones primitivas recursivas.

ahora veamos la cota.

Sea cota $:\mathbb {N} ^{2}\rightarrow \mathbb {N}$

simplemente observemos que $\forall n\in \mathbb {N}$ $n^{2}\geq n\implies z^{2}\geq z\iff x^{2}+y^{2}\geq z$

tenemos que cota$(x,y)=x^{2}+y^{2}$ cumple con que z es a lo sumo cota$(x,y)$ por lo tanto el existencial está bien definido como primitivo recursivo. $\Box$

Ejercicio 2

Considere la función $g:\mathbb {N} \rightarrow \mathbb {N} {\text{ tal que }}g(x)$ devuelve el menor número $y$ que cumple que $\phi _{y}^{(1)}(y)\downarrow {\text{ y, además, }}\phi _{y}^{(1)}(y){\text{ termina en más de }}x{\text{ pasos. Demuestre que }}g(x)$ no es computable.

Solución [1]

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

Veamos, que otras cosas nos dice $g(x)$.

Si $g(x)=y$ esto nos dice que y es el mínimo programa que termina en una cantidad de pasos mayor a $x$. Pero entonces todos los programas menores a y o bien terminan en una cantidad menor o igual a $x$ 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$(y,y)$ que sabemos que no es computable. Esto es porque por lo anterior, solo tengo que comprobar si algúna cantidad $x'\leq x$ de pasos logra terminar $y$ 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_1 \leftarrow \phi_{e}(Z_2) \\ \quad \quad Z_2 \leftarrow Z_2 + 1 \\ \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 $y$ no termina en $x$ 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 $g(x)$ 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 $Img(g)$ no tiene cota.

Sea $y=max(Img(g))$ y $x$ los pasos en que termina $y$.

Sea Error al representar (función desconocida «\gt»): {\displaystyle x' \gt x_2 \gt x} los pasos en que termina $g(x_{2})$. 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 (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 \quad g(x_2) \lt y } pero entonces $y\notin Img(g)$ pues hay un programa más chico que termina en más de $x$ pasos.

$\quad g(x_{2})=y$ pero entonces $g(x_{2})$ termina en $x$ pasos.

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

$\psi _{p}(y)={\begin{cases}1\quad \phi _{y}(y)\downarrow \\0\quad {\text{caso contrario}}\end{cases}}=HALT(y,y)$

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

Notas

[1] Identidad no es, aunque es claramente un subconjunto. Que no es exactamente ${\mathcal {K}}$ se ve facil. Agarramos cualquier programa que nos devuelva $g(x)$ y le agregamos instrucciones que no hacen nada. Esa 'transformación' saca al programa de la imagen de 'g' pero sigue estando en ${\mathcal {K}}$. Sin embargo esta 'transformación' no es la única, no podriamos obtener todos los programas de ${\mathcal {K}}$. 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

$Conjunto:C_{2}$

Veamos el complemento de $C_{2}$

${\overline {C_{2}}}=\{x:\exists y\in \mathbb {N} \phi _{x}(2y)\downarrow \wedge \phi _{x}(2y)\leq 5\}$

como $\phi _{x}(2y)\leq 5\implies \phi _{x}(2y)\downarrow$ voy a mirar la desigualdad.

Veamos que ${\overline {C_{2}}}$ es un conjunto de índices.

Sea $x_{1}\neq x_{2},x_{1}\in {\overline {C_{2}}},\psi _{P1}=\psi _{P2},x_{1}=\#P1,x_{2}=\#P2$ por lo tanto $x_{2}\in {\overline {C_{2}}}$

Esto es equivalente a decir que \overline{C_2} es un conjunto de índices (ej. 9 práctica 5). Además $f(x)=2$ es una función que está en el conjunto mientras que $g(x)=6$ 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 ${\overline {C_{2}}}$ es c.e. Para esto debe existir una función parcial computable que decida la pertenencia a ${\overline {C_{2}}}$.

Sea $p(x)=(\exists t)({\text{STP}}(2l(t),x,r(t))\wedge r(SNAP(2l(t),x,r(t))[1]\leq 5))$

con $l(t)=y$ y $r(t)={\text{pasos}}$

pero esto es una minimización no acotada de un predicado primitivo recursivo. Por lo tanto $p(x)$ es parcial computable y decide la pertenencia a ${\overline {C_{2}}}$ implica que $l(t)=y$ es c.e.

Pero ${\overline {C_{2}}}$ no es computable $\implies {\overline {C_{2}}}$ no es co.ce.

Resumiendo:

$C_{2}$ no computable. $C_{2}$ co.ce. $C_{2}$ no ce. $\Box$

$Conjunto:C_{1}$

Parece que este conjunto es reducible a Tot.

Quiero una f tal que $\phi _{x}$ es total sii 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 \phi_{f(x)}(2y)\downarrow \wedge \phi_{f(x)}(2y)\gt 5 }

Sea

$g(x,y)={\begin{cases}6\quad {\text{si }}\phi _{x}(2y)\\\uparrow \quad {\text{caso contrario}}\end{cases}}$

Como g es parcial computable, existe e : $\phi _{e}(x,y)=g(x,y)$

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

$\phi _{S(x,e)}(2y)=\phi _{e}(x,y)$

Veamos que $x\in {\text{Tot}}\iff f(x)\in C_{1},{\text{con }}f(x)=S(x,e)$

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 }

$x\notin {\text{Tot}}\implies \exists y\in \mathbb {N} :\phi _{x}(2y)\uparrow \implies g(x,y)\uparrow \implies \phi _{e}(x,y)\uparrow \implies \phi _{f(x)}(2y)\uparrow \implies f(x)\notin C_{2}$

como f es p.r. ${\text{Tot}}\leq C_{1}$.

$C_{1}$ no es c.e, ni co.ce, ni computable ni p.r $\Box$

Ejercicio 4

Decida y justifique si existe un e tal que para todo x, $\phi _{e}^{(1)}(x)\downarrow {\text{ sii }}\phi _{x}^{(1)}(e)\downarrow$

Solución

Sea $f:\mathbb {N} ^{2}\rightarrow \mathbb {N}$

$f={\begin{cases}1\quad {\text{si }}\phi _{x}(u)\downarrow \\\uparrow \quad {\text{caso contrario}}\end{cases}}$

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

$\phi _{e}(x)=f(x,e)$

que cumple:

$\phi _{e}{x}\downarrow \iff f(x,e)\downarrow \iff \phi _{x}(e)$

El enunciado es verdadero $\Box$