El incremento unario transforma 11111 en una palabra de ¿qué longitud?
Añade un símbolo.
La entrada11111 tiene cinco símbolos en su representación unaria.
El algoritmo añade exactamente un1 al final sin eliminar los anteriores.
¿Un decisor puede quedarse ejecutándose indefinidamente en una entrada? Sí o no.
La parada total es parte de la definición.
Un decisor debe dar respuesta correcta y detenerse en toda entrada del dominio.
Una ejecución infinita carece de esa respuesta final.
Por tanto no puede ocurrir en un decisor; la respuesta es no.
¿No detenerse tras 1000 pasos demuestra no parada? Sí o no.
Podría detenerse en el paso 1001.
Mil pasos sin parada solo describen un prefijo finito de la ejecución.
Una máquina podría detenerse en el paso1001 o mucho después.
No se ha probado ejecución infinita y la respuesta es no.
¿Un reconocedor puede no detenerse en una entrada ajena al lenguaje? Sí o no.
Distingue reconocedor de decisor.
Un reconocedor debe aceptar tras tiempo finito las palabras del lenguaje y nunca aceptar una ajena.
Fuera del lenguaje puede rechazar o seguir ejecutándose sin terminar.
Así la respuesta es sí; exigir parada también en esos casos lo convertiría en decisor.
Esboza la contradicción que impide un decisor general de la parada.
Construye una máquina que hace lo contrario de la predicción sobre sí misma.
Supongamos que H(M,w) decide siempre la parada de cualquier máquina con su entrada.
Construimos D(p) que entra en bucle si H(p,p) predice parada y termina si predice no parada.
Ejecutamos D sobre su propia descripción.
Una predicción de parada obliga a bucle y una predicción de bucle obliga a parada, contradiciendo ambas respuestas posibles de H.
La construcción sería efectiva si H existiera, por lo que la hipótesis es imposible.