Edición de «Recuperatorio de computabilidad Verano 2018 (DC)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
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 se 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 \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 | 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. | Escribamos eso, queremos un f que se comporte como HALT. | ||
Sea | Sea 'e' el número del programa que computa la función 'g', sea 'P' el programa: | ||
<math>\text{A:} \quad | <math>\text{A:} \quad Z_1 \leftarrow \phi_{e}(Z_2) | ||
\\ | \\ | ||
\quad\quad | \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} | \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} | \text{C:}\quad \text{IF STP}(X_1, X_1, Z_2) = 1 \text{ GOTO T} | ||
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) \gt y \wedge (\exists x')_{\leq x} : y \text{ termina en x' pasos} | ||
\\ | \\ | ||
0 \quad\text{ si existe } x : \phi_e(x) | 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) | \uparrow \quad\text{ no existe } x: \phi_e(x) \gt 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) \gt 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 \gt 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) \gt 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)\gt 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' \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: | entonces hay tres casos: | ||
<math>\quad g(x_2) | <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>\quad g(x_2) = y </math> pero entonces <math>g(x_2)</math> termina en <math>x</math> pasos. | ||
<math>\quad g(x_2) | <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. | 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) \gt y </math> y podemos volver a re, rescribir | ||
<math>\psi_p(y) = | <math>\psi_p(y) = | ||
Línea 123: | Línea 123: | ||
=== Notas === | === Notas === | ||
[1] | [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 == | == Ejercicio 3 == | ||
Línea 132: | Línea 131: | ||
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) \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) | <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 === | === Solución === | ||
Línea 174: | Línea 173: | ||
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)\gt 5 </math> | ||
Sea | Sea |