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 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 <math>y</math> termina en algúna cantidad <math>x'\leq x</math> de pasos y en caso contrario es que se indefine. | 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. | ||