¿Por qué el problema indecidible en las máquinas de Turing es interesante desde un sentido práctico?

Análisis estático.

El análisis estático es el campo de análisis de programas sin ejecutarlos . Queremos entender algo sobre un programa para todas las entradas posibles , no solo las que podemos pensar en probar. Tiene muchas aplicaciones:

• herramientas de desarrollo, como detectar problemas comunes (“usar después de gratis”) y eliminar el código muerto
• seguridad: probar que un programa sigue una política de seguridad antes de ejecutarlo
• Computación de alta seguridad: verificar el código donde la falla es peligrosa o costosa como la aeronáutica

También es, como resulta, imposible ¹. Algo así como.

Cómo sabemos esto? El resultado se llama teorema de Rice y la definición y la prueba son un poco técnicas², pero hay una intuición simple: los problemas de análisis estático se encuentran sistemáticamente en el problema de detención . Esto significa que siempre habrá programas en los que no podamos responder una pregunta de análisis estático porque la respuesta depende de resolver el problema de detención.

Un aparte importante: esto no significa que nunca podamos responder la pregunta. Lo más probable es que podamos hacerlo para la mayoría de los programas. Pero sí significa que nunca podremos tener un programa de análisis estático que sea perfecto : siempre habrá programas en los que el analizador estático dé la respuesta incorrecta o realice bucles para siempre.

Tomemos un ejemplo simple: detectar código muerto. A veces es trivial:

si (falso) {
// ¡este código está muerto!
}

Un algoritmo para encontrar solo estos casos podría ser tan simple como una búsqueda de cadena para if (false) .

A veces es más complicado, pero aún es posible:

x = 10
y = 7
si (x == y) {
// ¡este código está muerto!
}

Un algoritmo para detectar cosas como esta se vuelve más complicado, pero aún se puede imaginar hacerlo. Aquí, por ejemplo, podríamos evaluar la mayor cantidad de código posible sin conocer las entradas de tiempo de ejecución. En este caso, dado que x e y están definidos estáticamente, podemos simplificar a if (false) .

Incluso si los valores de tiempo de ejecución están involucrados, puede ser posible:

x = readLine () // obtiene un número de STDIN
if (isOdd (2 * x)) {
// ¡este código está muerto!
}

El algoritmo para hacer esto es significativamente más complicado pero, intuitivamente, vemos que es posible: sabemos que dos veces cualquier número es par, y el compilador debería poder darse cuenta de eso dada la definición de isOdd . Y, de hecho, podemos hacer algo como esto evaluando el programa mientras tratamos a x como una variable simbólica.

Dada esta progresión, puede pensar que podemos encontrar algoritmos cada vez más potentes para resolver este problema para cualquier entrada. Y, de hecho, hay técnicas que llegan bastante lejos: hay un campo completo llamado interpretación abstracta que se enfoca en evaluar el código sin conocer sus entradas de tiempo de ejecución.

Pero, ¿y si el programa se viera así?

if (isCollatzConjectureTrue ()) {
// ¿es este código muerto?
}

La conjetura de Collatz es un problema abierto en la teoría de números: nadie lo ha probado de una manera u otra. Para determinar si este bloque de código está muerto, ¡el analizador estático tendría que demostrar resultados que la comunidad matemática aún no ha resuelto! Es mucho pedir una herramienta que enfrenta lo que inicialmente parecía ser un problema simple.

Pero bueno, la conjetura de Collatz es cierta o no lo es³. Quizás podríamos escribir un analizador estático capaz de resolverlo.

Lo que nos dice el problema de detención para las máquinas de Turing, a través del teorema de Rice, es que incluso si escribiéramos un analizador tan poderoso, todavía habría casos que no podría manejar. Nunca seremos perfectos, no importa cuán buenos seamos.

Saber esto cambia cómo funciona todo el campo del análisis estático. La gente no pierde el tiempo tratando de encontrar algoritmos exactos : sabemos que es imposible. En cambio, a las personas se les ocurren buenas aproximaciones que se ajustan al problema. En el caso de la eliminación del código muerto, es mejor omitir algunos casos que marcar el código que está realmente vivo; en el caso de la seguridad, es mejor marcar el código que está bien que permitir una vulnerabilidad de seguridad.

El tipo de herramientas de programación que estamos interesados ​​en desarrollar, y el tipo con el que estamos contentos, es diferente porque conocemos las limitaciones fundamentales de lo que podemos hacer . Eso es absolutamente relevante para cualquier persona involucrada en herramientas de desarrollo, seguridad y verificación, así como, indirectamente, cualquier persona que use productos que dependen de estas cosas. (Casi todos.)

Y todo vuelve al humilde problema de Halting.

notas al pie
¹ Estoy eludiendo un detalle importante: solo es imposible si nos preocupamos por el comportamiento del programa en lugar del texto. Los problemas de análisis estático como “este programa define una variable llamada x ” son completamente posibles.

A menos que su idioma tenga la facilidad de crear variables en tiempo de ejecución como la mayoría de los lenguajes de script (es decir, eval y JavaScript de JavaScript) …

² En realidad no es tan técnico, solo necesita saber un poco sobre las máquinas Turing. No quería exponer los detalles en esta respuesta, pero es mucho más accesible que su resultado promedio en CS teórica. La Introducción de Sipser a la Teoría de la Computación tiene una excelente visión general muy legible en su sección sobre computabilidad.

³ Al menos supongo que este es el caso.

Si un programa es un virus resulta indecidible, lo que tiene enormes implicaciones para la seguridad. Ver Geneseo CSci 141 Undecidable Virus Detection para una prueba.

No sé si lo considera práctico, pero existen ciertas limitaciones en el sistema de tipos del lenguaje de programación Idris debido al problema de detención. Sin él, el sistema de tipos sería más fácil de usar, y algo así probablemente se habría implementado hace años porque hubiera sido mucho más simple hacerlo.

Esencialmente, sin el Problema de detención, escribir programas de computadora sería mucho más fácil de hacer con los idiomas que lo ayudan a evitar errores que los que tenemos ahora, suponiendo que no haya otro problema en su lugar.

Dicho esto, el problema de detención está básicamente codificado en cómo funcionan las matemáticas y la lógica. Es realmente difícil teorizar adecuadamente sobre cómo se verían las cosas sin él.

Debido al problema de detención.

Al interpretar las máquinas de Turing como programas, puede decir que no existe un programa especial que dado cualquier otro programa y entrada puede decir si ese programa se detendrá en esta entrada.

Un ejemplo muy práctico de mi operador hace mucho tiempo. Mi jefe estaba vendiendo un proyecto a una compañía, le asignó un equipo y ellos lo implementaron. El proyecto era una oferta de precio fijo (es decir, acordamos entregarlo por algún dinero previamente acordado) y no pareció funcionar muy bien. El equipo gastó muchos recursos y entregó muy pocos o ningún resultado. Entonces, el jefe nos envió a un colega y a mí para hacer una revisión del proyecto y ayudarlos a cumplir con el presupuesto.

Fuimos a ver las especificaciones, los entregables, la línea de tiempo … todo. Después de unos tres días nos miramos con cierto tipo de incredulidad. Hombre, están tratando de resolver el problema de Turing. Así que volvimos al jefe entregando la mala noticia, que ha vendido la solución del problema de detención como una entrega a precio fijo. Sabes que si era tiempo y material, podría haber sido el negocio del año …

Su primera reacción fue: ¿Por qué eres tan negativo? Te envié a entregar resultados. Tomó un tiempo convencerlo (no estoy seguro incluso ahora de que realmente tengamos éxito) de que no fue a nosotros a quien culpar, ni siquiera al equipo en el campo sino al pobre viejo Turing.

Así que aquí hay una aplicación práctica.

Es importante saber que algunos problemas son indecidibles. Después de un tiempo, desarrollas una intuición y puedes “sentir” que un problema es tal … luego se puede probar.

Por ejemplo, sería bueno si pudiéramos desarrollar un programa optimizador que pudiera tomar como entrada un programa arbitrario y producir uno equivalente que realice la misma función con el menor tiempo de ejecución (o usando la menor memoria, etc.). Es obvio por ese “sentimiento” que tal programa no puede ser construido.

Escuché una anécdota de que una corporación informática muy grande financió un proyecto para desarrollar dicho programa a fines de la década de 1950, si tan solo el grupo contuviera a alguien familiarizado con la teoría de la conputabilidad. Importa poco si esto es solo una leyenda urbana contada a los crédulos aspirantes a científicos informáticos, como era yo entonces, en 1972. Podría ser cierto.