El problema de la parada y la indecidibilidad

El problema de la parada, que consiste en decidir si un programa dado se detiene con una entrada determinada, es el ejemplo canónico de un problema algorítmicamente indecidible, y las reducciones a partir de él demuestran la indecidibilidad de muchos otros.

Definition

Un problema de decisión es indecidible si ninguna máquina de Turing lo decide correctamente para todas las entradas; el problema de la parada pregunta si una máquina arbitraria se detiene con una entrada arbitraria, y es el problema indecidible prototípico a partir del cual se demuestra la indecidibilidad de otros mediante reducción.

Scope

Este tema abarca la formulación precisa del problema de la parada, su prueba de indecidibilidad mediante diagonalización, la técnica de reducción muchos-a-uno para transferir la indecidibilidad, el teorema de Rice sobre propiedades no triviales de los programas, y problemas clásicos indecidibles como el Entscheidungsproblem y el problema de la palabra para grupos.

Core questions

• ¿Por qué no existe un algoritmo que decida si los programas se detienen?
• ¿Cómo se utilizan las reducciones para demostrar la indecidibilidad de un problema a partir de otro?
• ¿Qué dice el teorema de Rice sobre la decisión de propiedades de los programas?
• ¿Qué problemas matemáticos famosos resultaron ser indecidibles?

Key theories

Irresolubilidad del problema de la parada

Un argumento diagonal muestra que asumir un decisor de parada conduce a una contradicción, por lo que ningún algoritmo puede decidir la parada para todos los programas y entradas.

Reducción y transferencia de indecidibilidad

Si un problema conocido indecidible se reduce a un problema objetivo, el objetivo también es indecidible, lo que convierte la reducción en la herramienta estándar para establecer la indecidibilidad.

Teorema de Rice

Toda propiedad no trivial de la función calculada por un programa es indecidible, por lo que esencialmente ninguna propiedad de comportamiento interesante de los programas puede decidirse algorítmicamente.

Clinical relevance

Los resultados de indecidibilidad establecen límites estrictos al razonamiento automatizado y al análisis de programas: demuestran que no pueden existir herramientas generales perfectas para verificar la terminación o las propiedades de los programas, y explican por qué muchos problemas en lógica, álgebra y teoría de números no tienen solución algorítmica.

History

Turing y Church demostraron en 1936 que el Entscheidungsproblem, la cuestión de un algoritmo que decidiera la validez de primer orden, es irresoluble, con el problema de la parada en el centro del argumento de Turing. Rice generalizó el fenómeno en 1953, y la indecidibilidad se estableció más tarde para problemas concretos como el problema de la palabra para grupos por Novikov y el décimo problema de Hilbert por Matiyasevich.

Key figures

• Alan Turing
• Alonzo Church
• Henry Gordon Rice
• Pyotr Novikov

Seminal works

• sipser2013
• turing1936
• rogers1987

Frequently asked questions

¿Por qué un ordenador más rápido no puede resolver el problema de la parada?

La indecidibilidad es independiente de la velocidad o la memoria: el argumento diagonal descarta cualquier algoritmo, sin importar cuánto tiempo se le dé. El problema de la parada es irresoluble en principio, no meramente impracticable.

¿Podemos saber alguna vez si un programa se detiene?

A menudo sí para programas particulares, mediante análisis o ejecutándolos. Lo que es imposible es un único algoritmo que responda correctamente a la pregunta para cada programa y entrada. Por lo tanto, los verificadores de terminación prácticos solo tienen éxito en clases restringidas o pueden no dar una respuesta.