¿Cuáles son algunos ejemplos de informática, matemáticas o algoritmos donde se aplica el problema de detención?

El “problema de detención” se aplica prácticamente en cualquier momento que desee saber si se puede analizar un programa.

La detención del problema es lo menos interesante al respecto. La pregunta es si el programa puede alcanzar algún estado en particular. El estado de detención resulta ser fácil, objetivo, simple de describir.

Es fácil transformar otros problemas en el problema de detención. Supongamos, por ejemplo, que desea demostrar que un programa en particular nunca usa más de, digamos, 1 meg de memoria. Si tuviera dicho programa, podría convertirlo en un programa que resuelva el problema de detención: simplemente transforme el estado de detención en el estado “asignar un megabyte de memoria”. Como no existe un programa de detención, ese estimador de memoria general tampoco puede existir.

Descarta grandes clases de optimizadores y analizadores. Por lo tanto, las personas que escriben analizadores tienen que pensar en formas inteligentes de repensar sus preguntas en problemas que no se pueden resolver. Uno de mis favoritos es el verificador de código de bytes JVM, que hace muchas promesas como “este programa nunca desbordará la pila”. Lo hace restringiendo qué tipos de programas se pueden escribir. De hecho, existen programas JVM perfectamente seguros que no se pueden ejecutar porque no siguen las restricciones. Y el lenguaje Java está diseñado para no generar ese tipo de archivos de clase.

Entonces, el problema de detención tiene una aplicabilidad muy amplia … pero no porque las cosas se detengan o no.

En general, solo te dice que algunas cosas que te gustaría hacer son imposibles.

Por ejemplo, supongamos que le digo que he escrito un programa que puede ver su código fuente y decirle de manera confiable si su programa tiene un error o no. Esa sería una afirmación impresionante, pero ¿puede ser verdad?

Bueno, no, no puede ser. Puede ajustar su programa en un ciclo ‘while’ que lo ejecuta una y otra vez hasta que produzca la respuesta que desea. Si tiene un error, podría ejecutarse para siempre, pero si funciona bien, eventualmente se detendrá. Alimente eso en mi “detector de errores” y no necesariamente podrá decirle si tiene un error o no.

El problema de detención dice que no puedo escribir un programa que distinga de manera confiable las versiones defectuosas de ese programa de las versiones correctas … para que sepa que mi reclamo es falso. Dado que el cerebro humano parece actuar como una máquina de Turing, es probable que ningún humano pueda decirle de manera confiable si un programa tiene un error o no. Ningún departamento de control de calidad puede decirle eso de manera confiable.

Dicho esto, en mis 40 años como programador, dudo que haya recurrido al problema de la detención más de un par de veces para probar algún punto importante.

Lo que pasa es que no dice que no se puede saber si un programa en particular se detendrá o no. Hay grandes clases de programas donde puedes encontrar un “while (verdadero) / * no hacer nada * /;” en alguna parte definitivamente ejecutada del código y decir, con seguridad “¡Este programa no se detendrá!” – y hay grandes clases de programas sin bucles ilimitados y sin recursividad que pueda decir “¡Esto definitivamente se detendrá!”. Lo que dice Turing es que hay algunos programas que no puedes ver.

Peor aún, la prueba de la insolubilidad del problema de detención no nos da idea de qué tipo de programas patológicos podrían ser así. Dice que existen, pero no cómo son.

Ciertamente, es posible diseñar sistemas informáticos bastante útiles que NO estén completos para Turing, para lo cual el problema de detención PUEDE resolverse. Esto se hizo de verdad en las primeras versiones de los lenguajes de programación GLSL y HLSL (utilizados en las GPU para renderizar gráficos). Esos lenguajes originalmente le prohibieron usar bucles ilimitados o recursividad, y aplicaron esas reglas en sus respectivos compiladores, e hicieron completamente imposible escribir un programa que no se detuviera.

Lamentablemente, esos idiomas no son “completos de Turing”, por lo que había muchas cosas que no se podían escribir con ellos … pero dado que es esencial que todos los programas GLSL y HLSL se detengan, eso no fue algo tan terrible.