Edición de «Recuperatorio de computabilidad Verano 2018 (DC)»

== Ejercicio 1 ==

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

<math>
\text{pitagórica}(3,4)=1 
</math>

<math>
\text{pitagórica}(2,3)=0
</math>

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

=== Solución ===

Quiero ver que existe un <math>z</math> tal que: <math>x^2+y^2=z^2</math> y que lo puedo hallar de forma primitiva recursiva.

pitagórica<math>(x,y)=(\exists z)_{\le cota(x,y)}p(z,x,y)</math>

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

ahora veamos la cota.

Sea cota <math> : \mathbb{N}^2 \rightarrow \mathbb{N} </math>

simplemente observemos que 
<math>\forall n \in \mathbb{N}</math>  <math> n^2 \ge n \implies z^2 \geq z \iff x^2+y^2 \geq z</math>

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

== Ejercicio 2 ==

Considere la función <math>g:\mathbb{N}\rightarrow\mathbb{N} \text{ tal que } g(x)</math> devuelve el menor número <math>y</math> que cumple que <math>\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) </math> no es computable.

=== Solución ===

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

Veamos, que otras cosas nos dice <math>g(x)</math>.

Si <math>g(x) = y</math> esto nos dice que '''y''' es el '''mínimo''' programa que termina en una cantidad de pasos mayor a <math>x</math>.
Pero entonces '''todos''' los programas ''menores'' a '''y''' o bien terminan en una cantidad menor o igual a <math>x</math> 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 <math>g(x) = y_2 \gt y</math> entonces resolví HALT<math>(y,y)</math> que sabemos que no es computable. 
Esto es porque por lo anterior, solo tengo que comprobar si algúna cantidad <math>x'\leq x</math> de pasos logra terminar <math>y</math> 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:

<math>\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</math>

Para ser más claro:

<math>\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}</math>

Pero si <math>y</math> no termina en <math>x</math> 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 <math>g(x)</math> pues este era el mínimo, esto es absurdo, así que debe indefinirse.

Por lo tanto re escribimos,

<math>\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}</math>

Ahora solo queda ver que siempre existe un <math>x:g(x)\gt y</math>. 

Veamos que <math>Img(g)</math> no tiene cota.

Sea <math>y = max(Img(g))</math> y <math>x</math> los pasos en que termina <math>y</math>.

Sea <math>x' \gt x_2 \gt x</math> los pasos en que termina <math>g(x_2)</math>. 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:

<math>\quad g(x_2) \lt y </math> pero entonces <math>y \notin Img(g)</math> pues hay un programa más chico que termina en más de <math>x</math> pasos.

<math>\quad g(x_2) = y </math> pero entonces <math>g(x_2)</math> termina en <math>x</math> pasos.

<math>\quad g(x_2) \gt y </math> entonces <math>y</math> 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 <math>x : g(x) \gt y </math> y podemos volver a re, rescribir

<math>\psi_p(y) = 
\begin{cases}
1 \quad \phi_y(y) \downarrow
\\
0 \quad \text{caso contrario}
\end{cases} =  HALT(y, y) </math>

Computamos HALT que sabemos que no es computable, por lo tanto 'g' no es computable. <math>\Box </math>

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

<math>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 </math>
<math>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 </math>

=== Solución ===

==== <math>Conjunto: C_2</math> ====

Veamos el complemento de <math>C_2</math>

<math>\overline{C_2} = \{ x: \exists y\in\mathbb{N} \phi_x(2y) \downarrow \wedge \phi_x(2y) \leq 5 \}</math>

como <math>\phi_x(2y) \leq 5 \implies \phi_x(2y)\downarrow</math> voy a mirar la desigualdad.

Veamos que <math>\overline{C_2}</math> es un conjunto de índices. 

Sea <math>x_1\neq x_2, x_1 \in \overline{C_2}, \psi_{P1} = \psi_{P2}, x_1=\#P1, x_2=\#P2</math> 
por lo tanto <math>x_2 \in \overline{C_2}</math>

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

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

con <math>l(t)=y</math> y <math>r(t)=\text{pasos}</math>

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

Pero <math>\overline{C_2}</math> no es computable <math>\implies \overline{C_2}</math> no es co.ce. 

Resumiendo:

<math>C_2</math> no computable.
<math>C_2</math> co.ce.
<math>C_2</math> no ce. <math>\Box</math>

==== <math>Conjunto: C_1</math> ====

Parece que este conjunto es reducible a Tot.

Quiero una f tal que <math>\phi_x</math> es total '''sii''' <math>\phi_{f(x)}(2y)\downarrow \wedge \phi_{f(x)}(2y)\gt 5 </math>

Sea

<math>g(x,y) = \begin{cases}
6 \quad \text{si } \phi_x(2y) \\
\uparrow \quad \text{caso contrario}
\end{cases}</math>

Como ''g'' es parcial computable, existe ''e'' : <math>\phi_e(x,y) = g(x,y)</math>

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

<math> \phi_{S(x,e)}(2y) = \phi_e(x,y) </math>

Veamos que <math>x\in\text{Tot} \iff f(x) \in C_1, \text{con } f(x) = S(x,e)</math>

<math>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 </math>

<math>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</math>

como ''f'' es p.r. <math>\text{Tot}\leq C_1</math>.

<math>C_1</math> no es c.e, ni co.ce, ni computable ni p.r <math>\Box</math>

== Ejercicio 4 ==

Decida y justifique si existe un ''e'' tal que para todo ''x'', <math>\phi_e^{(1)}(x)\downarrow \text{ sii } \phi_x^{(1)}(e)\downarrow</math>

=== Solución ===

Sea <math>f:\mathbb{N}^2 \rightarrow \mathbb{N}</math>

<math> f = \begin{cases}
1 \quad \text{si } \phi_x(u) \downarrow 
\\
\uparrow \quad \text{caso contrario}
\end{cases}</math>

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

<math> \phi_e(x) = f(x,e) </math>

que cumple:

<math> \phi_e{x} \downarrow \iff f(x,e) \downarrow \iff \phi_x(e) </math>

El enunciado es verdadero <math>\Box</math>