Diferencia entre revisiones de «Recuperatorio de computabilidad Verano 2018 (DC)»
| (No se muestran 5 ediciones intermedias de 4 usuarios) | |||
| Línea 20: | Línea 20: | ||
con <math>p</math> el predicado: <math> p(t,x,y) = (t^2 = x^2+y^2)</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 | Vemos que <math>p</math> es primitivo recursivo por ser composición de funciones primitivas recursivas. | ||
ahora veamos la cota. | ahora veamos la cota. | ||
| Línea 44: | Línea 44: | ||
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. | 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 | 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 > 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 | Esto es porque por lo anterior, solo tengo que comprobar si <math>y</math> termina en algúna cantidad <math>x'\leq x</math> de pasos y en caso contrario es que se indefine. | ||
Escribamos eso, queremos un f que se comporte como HALT. | 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: | Sea '''e''' el número del programa que computa la función '''g''', sea '''P''' el programa: | ||
<math>\text{A:} \quad Z_2 \leftarrow Z_2 + 1 \text{ // el cero no nos interesa} | <math>\text{A:} \quad Z_2 \leftarrow Z_2 + 1 \text{ // el cero no nos interesa} | ||
| Línea 72: | Línea 72: | ||
<math>\psi_p(y) = | <math>\psi_p(y) = | ||
\begin{cases} | \begin{cases} | ||
1 \quad\text{ si existe } x : \phi_e(x) | 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) | 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) | \uparrow \quad\text{ no existe } x: \phi_e(x) > y | ||
\end{cases}</math> | \end{cases}</math> | ||
| Línea 86: | Línea 86: | ||
<math>\psi_p(y) = | <math>\psi_p(y) = | ||
\begin{cases} | \begin{cases} | ||
1 \quad\text{ si existe } x : \phi_e(x) | 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 | 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) | \uparrow \quad\text{ no existe } x: \phi_e(x) > y | ||
\end{cases}</math> | \end{cases}</math> | ||
Ahora solo queda ver que siempre existe un <math>x:g(x) | Ahora solo queda ver que siempre existe un <math>x:g(x) > y</math>. | ||
Veamos que <math>Img(g)</math> no tiene cota. | Veamos que <math>Img(g)</math> no tiene cota. | ||
| Línea 99: | Línea 99: | ||
Sea <math>y = max(Img(g))</math> y <math>x</math> los pasos en que termina <math>y</math>. | Sea <math>y = max(Img(g))</math> y <math>x</math> los pasos en que termina <math>y</math>. | ||
Sea <math>x' | Sea <math>x' > x_2 > 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: | entonces hay tres casos: | ||
<math>\quad g(x_2) | <math>\quad g(x_2) < 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) = y </math> pero entonces <math>g(x_2)</math> termina en <math>x</math> pasos, no en <math>x'</math> pasos. | ||
<math>\quad g(x_2) | <math>\quad g(x_2) > y </math> pero 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. | 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) | Es decir siempre va a existir un <math>x : g(x) > y </math> y podemos volver a re, rescribir | ||
<math>\psi_p(y) = | <math>\psi_p(y) = | ||
| Línea 132: | Línea 132: | ||
Decida y justifique si los siguientes conjuntos son p.r, c.e., co-c.e o computables: | 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) | <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) > 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) | <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) > 5 </math> | ||
=== Solución === | === Solución === | ||
| Línea 174: | Línea 174: | ||
Parece que este conjunto es reducible a Tot. | 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) | Quiero una f tal que <math>\phi_x</math> es total '''sii''' <math>\phi_{f(x)}(2y)\downarrow \wedge \phi_{f(x)}(2y) > 5 </math> | ||
Sea | Sea | ||
Revisión actual - 18:48 22 feb 2021
Ejercicio 1[editar]
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[editar]
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[editar]
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][editar]
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 pasos.
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 y podemos volver a re, rescribir
Computamos HALT que sabemos que no es computable, por lo tanto 'g' no es computable.
Notas[editar]
[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[editar]
Decida y justifique si los siguientes conjuntos son p.r, c.e., co-c.e o computables:
Solución[editar]
[editar]
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
![{\displaystyle p(x)=(\exists t)({\text{STP}}(2l(t),x,r(t))\wedge r(SNAP(2l(t),x,r(t))[1]\leq 5))}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/351451a37fe9959288b370383e9da5d181bd3359)
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.
[editar]
Parece que este conjunto es reducible a Tot.
Quiero una f tal que es total sii
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 (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 }
como f es p.r. .
no es c.e, ni co.ce, ni computable ni p.r
Ejercicio 4[editar]
Decida y justifique si existe un e tal que para todo x,
Solución[editar]
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
