Problema de la parada

El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing y una palabra , determinar si terminará en un número finito de pasos cuando es ejecutada usando como dato de entrada. Alan Turing, en su famoso artículo "On Computable Numbers, with an Application to the Entscheidungsproblem" (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible (no computable o no recursivo), en el sentido de que ninguna máquina de Turing lo puede resolver.

Relevancia en la práctica

Al ejecutar un programa, este puede terminar después de un número finito de pasos o puede nunca terminar. En la práctica, este último caso se manifiesta como programas que se quedan " trabados" o que entran a un bucle infinito. Por esta razón sería de gran utilidad resolver la siguiente pregunta en la práctica:

Existe un programa P, tal que, dado un programa cualquiera q y unos datos de entrada x, muestre como salida 1 si q con entrada x termina en un número finito de pasos o muestre como salida 0 si q con x entra a un bucle infinito.

Conocer si existe el programa P es, en términos resumidos, el problema de la parada.

Sin embargo hay que hacer notar que la sabiduría popular acerca de este problema hace pensar que nunca es posible demostrar que un programa termina. Esto es absolutamente falso, y procede de la negación errónea de un causal, y de otras falacias políticas intencionadas.

Lo que se afirma es que no existe una manera automática computable de saber si todos los programas del mundo terminan. No se niega que exista la prueba para programas concretos. De hecho, la construcción de pruebas para programas concretos es un paso obligatorio para demostrar su correctitud.

El procedimiento para construir estas pruebas no es automático, sin embargo, existen heurísticas que facilitan encontrar las pruebas de los programas. El área de conocimiento que estudia la construcción sistemática de pruebas se denomina Análisis de Terminación.

La evaluación o ejecución del programa con las entradas sin embargo no constituye una prueba de que siempre termine, sino de que en las circunstancias de la ejecución, terminó.

Other Languages