Indecidibilidad y el problema de la parada

El problema de la parada pregunta si un programa dado se detiene eventualmente con una entrada dada, y la prueba de Turing de que ningún algoritmo puede responder esto para todos los casos es el ejemplo fundacional de un problema indecidible.

Definition

Un problema de decisión es indecidible cuando ningún algoritmo puede responderlo correctamente para cada entrada; el problema de la parada, que decide si un programa arbitrario se detiene con una entrada arbitraria, es el problema indecidible canónico, probado como tal mediante un argumento diagonal autorreferencial.

Scope

Este tema cubre el argumento de diagonalización que establece la indecidibilidad del problema de la parada, la distinción entre problemas decidibles, reconocibles y co-reconocibles, el teorema de Rice que muestra que todas las propiedades semánticas no triviales de los programas son indecidibles, y el catálogo de problemas indecidibles naturales en lógica, matemáticas y ciencias de la computación.

Core questions

• ¿Por qué ningún algoritmo único puede decidir si cada programa se detiene?
• ¿Cuál es la diferencia entre que un problema sea decidible y meramente reconocible?
• ¿Por qué son indecidibles esencialmente todas las propiedades interesantes del comportamiento de los programas?
• ¿Cómo se propaga la indecidibilidad del problema de la parada a otros problemas?

Key theories

Indecidibilidad del problema de la parada

Asumir un algoritmo que decide la parada lleva a una contradicción a través de un programa que se detiene exactamente cuando se predice que no lo hará, por lo que tal algoritmo no puede existir.

Teorema de Rice

Toda propiedad no trivial de la función calculada por un programa —cualquier cosa que se cumpla para algunos programas y falle para otros basándose en el comportamiento— es indecidible, generalizando el resultado de la parada a todas las propiedades semánticas.

Clinical relevance

Debido a que la parada y, por el teorema de Rice, todas las propiedades de comportamiento no triviales de los programas son indecidibles, ninguna herramienta puede detectar perfectamente bucles infinitos, verificar la corrección arbitraria o analizar completamente cada programa; los analizadores estáticos y verificadores deben, por lo tanto, aproximar, aceptar falsas alarmas o restringir su alcance.

History

Turing estableció la indecidibilidad del problema de la parada y del problema de decisión para la lógica en 1936 utilizando un argumento diagonal inspirado en Cantor y Gödel. Rice probó su generalización de gran alcance en 1953, y durante las décadas siguientes muchos problemas naturales, incluido el décimo problema de Hilbert sobre ecuaciones diofánticas, se demostraron indecidibles.

Key figures

• Alan Turing
• Henry Gordon Rice
• Emil Post
• Alonzo Church

Seminal works

• turing1937
• sipser2013

Frequently asked questions

¿Por qué no podemos simplemente ejecutar un programa para ver si se detiene?

Ejecutarlo solo le dirá que se detuvo si realmente lo hace; si va a ejecutarse indefinidamente, ninguna espera finita lo revelará. El problema de la parada exige un método que siempre dé la respuesta correcta en un tiempo finito para cada programa y entrada, y Turing demostró que tal método no existe.

¿La indecidibilidad hace que el análisis de programas sea inútil?

No, pero explica por qué el análisis perfecto es imposible. Las herramientas se las arreglan siendo conservadoras, señalando cualquier cosa que no puedan probar que sea segura, manejando clases restringidas de programas de manera exacta, o resolviendo muchos casos prácticos mientras admiten que pueden fallar en casos adversarios o patológicos.