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 35: | Línea 35: | ||
Considere la función <math>g:\mathbb{N}\rightarrow\mathbb{N} \text{ tal que } g(x)</math> devuelve el menor número <math>y</math> que cumple que <math>\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) </math> no es computable. | Considere la función <math>g:\mathbb{N}\rightarrow\mathbb{N} \text{ tal que } g(x)</math> devuelve el menor número <math>y</math> que cumple que <math>\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) </math> no es computable. | ||
=== Solución | === Solución === | ||
La imagen de <math>g</math> son programas que terminan cuando se los valua en su propio número de programa. Uno está tentado en hacer una reducción a <math>\mathcal{K}</math> pero esto no parece funcionar. [[#Notas|[ | La imagen de <math>g</math> son programas que terminan cuando se los valua en su propio número de programa. Uno está tentado en hacer una reducción a <math>\mathcal{K}</math> pero esto no parece funcionar. [[#Notas|[1]]] | ||
Veamos, que otras cosas nos dice <math>g(x)</math>. | Veamos, que otras cosas nos dice <math>g(x)</math>. |