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 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} : \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) \gt 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) \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> pasos, no 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) \gt 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) \gt 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) \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 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)\gt 5 </math> | ||
Sea | Sea |