Descargo de responsabilidad: para comprender la respuesta, primero, debe completar otra prueba, lo que me permite hacer esa, con la primera prueba haciendo que la respuesta sea más comprensible para los no especialistas.
Como la mayoría de las cosas en la teoría de la computación, las matemáticas generalmente se interponen en la comprensión del concepto. Una vez que entiendes el concepto, es fácil reinsertar las matemáticas. En este caso particular, veamos un diálogo hipotético entre las dos personas para discernir el problema, convirtiendo sus ideas en matemáticas más adelante.
Ada : Cada vez que encontramos algún problema que nos obliga a aumentar la potencia de cálculo, ‘Babbage nunca puede construir una máquina para ejecutar mi software. Cada vez que intento hacer algo con bucles, funciona bien con una excepción: casos en los que es imposible saber si algún bucle será infinito o terminará.
Alan : Me pregunto por qué sucede esto solo en bucles de duración indeterminada. ¿A ver si podemos razonar esto?
Ada : OK, tienes razón en que el problema es la duración realmente indeterminada, no si los bucles son infinitos.
Alan : ¿Estás de acuerdo en que cuando algo no se repite, tiene una duración determinada, mientras que cualquier cosa que tenga una longitud infinita también es determinada? Además, ¿está de acuerdo en que, debido a la inducción (también conocida como recursión), podemos decir que cualquier bucle de longitud finita tiene un tiempo de ejecución determinado?
Ada : Sí … pero déjame verificar el paso recursivo ……
1. Si es cierto para ningún ciclo, y también es cierto para un ciclo, entonces debe ser cierto para dos ciclos.
2. Si se sabe que un ciclo dado termina en una cantidad de tiempo finita, entonces sabemos que un ciclo de una longitud más que el ciclo original también terminará en una cantidad de tiempo finita ……… OK, eso tiene sentido ahora.
Alan : Bien … Pero, ¿por qué no podemos hacer que todos nuestros bucles sean probablemente infinitos o probablemente finitos?
Ada : No veo ninguna razón por la que no podamos, pero intentemos algunos casos para ver si funciona. Para cualquier programa dado, siempre puedo esperar para ver si termina, suponiendo que pueda esperar para siempre. Como eso no funcionará, ¿qué programas funcionarán? Los programas procesan sus entradas para producir salidas, y digamos que una de las entradas implica decidir si una copia de sí misma terminará alguna vez. ¡Ese es un caso interesante que parece representar la cúspide del problema!
Alan : Tienes razón (guiño) … No puedo hacer preguntas sobre mí si tienen que ver con mi posible terminación, eso es demasiado desagradable. Digamos que mi programa termina; el monitor también terminará. Si no termina, nunca terminaré. De cualquier manera, es decidible, aunque todavía estamos atrapados con casos indeterminados que son indecidibles.
Ada : Bingo! Creo que tienes algo allí: siempre podemos decidir si un bucle es finito o infinito. Sin embargo, no podemos decidir sobre bucles indeterminados, y la forma de forzar uno indeterminado es ejecutar un detector de terminación de bucle sobre sí mismo.
Alan : Tienes razón, ¡déjame escribir eso! ¿Suena “On Computable Numbers” como un buen título para el periódico? (Ada: Sí) ¡Pero, el OP preguntó sobre idiomas, no programas!
Ada : Eso es fácil para un alfabeto de cualquier tamaño (idioma). Podemos enumerar todas las cadenas posibles (programas), y si el programa es decidible, podemos poner un 0 en la cinta de una máquina Turing. Si es indecidible, pondremos un 1. Simplemente contamos los números de 0 y 1; eso es decidible para cualquier idioma. La enumeración siempre es decidible, porque en cualquier punto dado, tenemos un número finito. Y agregar 1 a un número finito también es finito.
Fin del dialogo
Formalicemos lo anterior:
La última declaración de Ada dice que para el lenguaje L, si introducimos todas las entradas posibles de la máquina M, como resultado siempre obtendremos uno de los símbolos en L. Es una máquina / programa decidible o indecidible, y esto implica que para un UTM, “L” es todos los programas posibles, incluido él mismo. Llame a esto L (M). Ahora es fácil ver que no hay diferencia entre L y L (M), así que digamos que L = L (M). Por lo tanto, dado que para aceptar necesitamos HALT L no es decidible.
