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) = |