Recuperatorio de computabilidad Verano 2018 (DC)

Ejercicio 1

Considere el predicado pitagórica: 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 \mathbb{N}^2 \rightarrow {0, 1} } que dados 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} 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 y} nos dice si 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^2+y^2} es un cuadrado perfecto, por ejemplo:

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 \text{pitagórica}(3,4)=1 }

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 \text{pitagórica}(2,3)=0 }

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

Solución

Quiero ver que existe 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 z} tal 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^2+y^2=z^2} y que lo puedo hallar de forma primitiva recursiva.

pitagóricaError 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,y)=(\exists z)_{\le cota(x,y)}p(z,x,y)}

con 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 p} el predicado: 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 p(t,x,y) = (t^2 = x^2+y^2)} . Vemos 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 p} es primitivo recursivo por ser composición de funciones primitivas recursivas.

ahora veamos la cota.

Sea cota 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 : \mathbb{N}^2 \rightarrow \mathbb{N} }

simplemente observemos 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 \forall n \in \mathbb{N}} 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 n^2 \ge n \implies z^2 \geq z \iff x^2+y^2 \geq z}

tenemos que cotaError 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,y)=x^2+y^2} cumple con que z es a lo sumo cotaError 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,y)} por lo tanto el existencial está bien definido como primitivo recursivo. 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 \Box}

Ejercicio 2

Considere la función 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:\mathbb{N}\rightarrow\mathbb{N} \text{ tal que } g(x)} devuelve el menor número 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 y} que cumple 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 \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 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} son programas que terminan cuando se los valua en su propio número de programa. Uno está tentado en hacer una reducción a 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 \mathcal{K}} pero esto no parece funcionar. [2]

Veamos, que otras cosas nos dice 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)} .

Si 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} esto nos dice que y es el mínimo programa que termina en una cantidad de pasos mayor a 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} . Pero entonces todos los programas menores a y o bien terminan en una cantidad menor o igual a 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} 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 > y} entonces resolví HALTError 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 (y,y)} que sabemos que no es computable. Esto es porque por lo anterior, solo tengo que comprobar si 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 y} termina en algúna cantidad 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'\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 (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 \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 (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 \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 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 y} no termina en 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} 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 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)} pues este era el mínimo, esto es absurdo, así que debe indefinirse.

Por lo tanto re escribimos,

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 \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 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:g(x) > y} .

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 Img(g)} no tiene cota.

Sea 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 y = max(Img(g))} y 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} los pasos en que termina 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 y} .

Sea 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' > x_2 > x} los pasos en que termina 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_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) < y } pero entonces 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 y \notin Img(g)} pues hay un programa más chico que termina en más de 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} pasos.

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) = y } pero entonces 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_2)} termina en 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} 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 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 f(x) = 2 } es una función que está en el conjunto mientras 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 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 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 \overline{C_2}} es c.e. Para esto debe existir una función parcial computable que decida la pertenencia a 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 \overline{C_2}} .

Sea 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 p(x) = (\exists t)(\text{STP}(2 l(t), x, r(t)) \wedge r(SNAP(2l(t), x, r(t))[1]\leq 5))}

con 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 l(t)=y} y 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 r(t)=\text{pasos}}

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

Pero 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 \overline{C_2}} no es computable 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 \implies \overline{C_2}} no es co.ce.

Resumiendo:

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 C_2} no computable. 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 C_2} co.ce. 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 C_2} no ce. 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 \Box}

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 Conjunto: C_1}

Parece que este conjunto es reducible a Tot.

Quiero una f tal 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 \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) > 5 }

Sea

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) = \begin{cases} 6 \quad \text{si } \phi_x(2y) \\ \uparrow \quad \text{caso contrario} \end{cases}}

Como g es parcial computable, existe 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 \phi_e(x,y) = g(x,y)}

por teo del parámetro existe una función primitiva recursiva S, tal 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 \phi_{S(x,e)}(2y) = \phi_e(x,y) }

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

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 \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. 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 \text{Tot}\leq C_1} .

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 C_1} no es c.e, ni co.ce, ni computable ni p.r 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 \Box}

Ejercicio 4

Decida y justifique si existe un e tal que para todo x, 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_e^{(1)}(x)\downarrow \text{ sii } \phi_x^{(1)}(e)\downarrow}

Solución

Sea 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 f:\mathbb{N}^2 \rightarrow \mathbb{N}}

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