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 ser 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 $g(x)=y_{2}>y$ entonces resolví HALT$(y,y)$ que sabemos que no es computable. Esto es porque por lo anterior, solo tengo que comprobar si $y$ termina en algúna cantidad $x'\leq x$ 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:

$\psi _{p}(y)={\begin{cases}1\quad {\text{ si existe }}x:\phi _{e}(x)>y\wedge (\exists x')_{\leq x}:\phi _{y}(y){\text{ termina en x' pasos}}\\0\quad {\text{ si existe }}x:\phi _{e}(x)>y\wedge (\forall x')_{\leq x}:\phi _{y}(y){\text{ no termina en x' pasos}}\\\uparrow \quad {\text{ no existe }}x:\phi _{e}(x)>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,

$\psi _{p}(y)={\begin{cases}1\quad {\text{ si existe }}x:\phi _{e}(x)>y\wedge (\exists x')_{\leq x}:\phi _{y}(y){\text{ termina en x' pasos}}\\0\quad {\text{ si existe }}x:\phi _{e}>y\wedge \phi _{y}(y){\text{ se indefine}}\\\uparrow \quad {\text{ no existe }}x:\phi _{e}(x)>y\end{cases}}$

Ahora solo queda ver que siempre existe un $x:g(x)>y$.

Veamos que $Img(g)$ no tiene cota.

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

Sea $x'>x_{2}>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:

$\quad g(x_{2})<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, no en $x'$ pasos.

$\quad g(x_{2})>y$ pero 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 $x:g(x)>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] 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 ${\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:

$C_{1}={x\in \mathbb {N} :{\text{para todo }}y\in \mathbb {N} ,\phi _{x}^{(1)}(2y)\downarrow }{\text{ y }}\phi _{x}^{(1)}(2y)>5$ $C_{2}={x\in \mathbb {N} :{\text{para todo }}y\in \mathbb {N} ,\phi _{x}^{(1)}(2y)\uparrow }{\text{ o }}\phi _{x}^{(1)}(2y)>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 $\phi _{f(x)}(2y)\downarrow \wedge \phi _{f(x)}(2y)>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 (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 }

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