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 $M$ y una palabra $w$, determinar si $M$ terminará en un número finito de pasos cuando es ejecutada usando $w$ 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 conjunto de programas, este puede terminar después de un número finito de pasos o puede no terminar nunca. 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 falso.

Lo que se afirma es que no existe una manera automática computable de saber si todos los programas posibles 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ó.

Irresolubilidad del problema

La irresolubilidad del problema se puede mostrar de varias formas, pero en esencia todas equivalen a un argumento diagonal de Cantor. A continuación se muestra el argumento en términos modernos de programación:

Supongamos que este problema sí se puede resolver algoritmicamente; entonces hay un programa, que llamaremos Termina, que cada vez que se le suministra el código de un programa p y sus datos de entrada x, hace un número finito de operaciones y responde «True» cuando el programa termina o «False» cuando el programa nunca termina. En lenguaje Python:

def Termina(p, x):
    #Supongamos que aquí se encuentra un código maravilloso que soluciona el problema de la parada
    #Esta función regresa True si p(x) termina o False en otro caso

Bajo la suposición de que existe este programa, se puede usar como subrutina de otro programa más grande, al que llamaremos «Diagonal» (en referencia a la diagonal de Cantor). Este programa recibirá como dato de entrada el código de un programa cualquiera w, y usará el programa Termina para decidir si el programa w termina cuando se le suministra ella misma como entrada (no hay nada de raro en esto, pues en la práctica hay programas como los compiladores que pueden suministrarse a sí mismos como dato de entrada). A continuación, Diagonal hace lo opuesto: Si w termina entonces Diagonal entra en un ciclo infinito y si w entra en un ciclo infinito entonces Diagonal termina. En lenguaje Python:

def Diagonal(w):
    if Termina(w, w):
        while True: pass #Esta instrucción es un bucle infinito

Resumiendo, el programa Diagonal está diseñado para tener la siguiente propiedad (entiéndase la flecha como «siempre y cuando»):

${\it {{Diagonal}(w){\text{ termina}}\iff w(w){\text{ nunca termina}}}}$

Como w puede ser el código de cualquier programa, particularmente puede ser el del mismo Diagonal:

def Diagonal(Diagonal):
     if Termina(Diagonal, Diagonal):
         while True: pass

En este caso se tiene $w=Diagonal$, y por lo tanto

${\it {{Diagonal}({\it {{Diagonal}){\text{ termina}}\iff {\it {{Diagonal}({\it {{Diagonal}){\text{ nunca termina}}}}}}}}}}$

Es decir que bajo la suposición de que existe el algoritmo Termina se llega a la paradójica conclusión de que hay una instrucción que termina siempre y cuando no termine. Como esta conclusión es absurda, entonces no puede existir el algoritmo Termina; es decir que es imposible resolver el problema de la parada algorítmicamente.

Demostración por construcción de máquinas de Turing

Es más común encontrar en los libros de texto la demostración anterior en términos de máquinas de Turing como sigue:

Supongamos que el problema de la parada tiene solución. Es decir, supongamos que existe una máquina de Turing que es capaz de determinar si otra máquina de Turing parará (terminará) con una entrada determinada. Llamemos Termina a esta máquina. Esta máquina recibiría como entrada la cadena $M,w$, donde $M$ es la codificación de una máquina de Turing y $w$ es la codificación de la cadena que se le alimenta a $M$. La máquina $Termina$ terminará en un estado de aceptación si $M$ para ante la entrada $w$, y en otro caso terminará en un estado de rechazo, pero nunca entrará en un ciclo infinito.

Es posible crear una máquina Copia que al recibir una cadena cualquiera $w$ termine en un estado de aceptación con $w,w$ en su cinta. Ahora crearemos una máquina Diagonal que recibe de entrada una cadena $w$, que presuntamente será la codificación de una máquina de Turing $M$. Primero Diagonal utilizará la máquina Copia para duplicar la cadena $w$, convirtiéndola en $w,w$. A continuación, Diagonal pasará este resultado a través de Termina para decidir si la máquina representada por $w$ para ante la cadena $w$ y realiza lo opuesto: Si Termina acepta, entonces Diagonal entra en un bucle infinito (que consiste de un solo estado al que se regresa una y otra vez) y en otro caso, si Termina rechaza entonces Diagonal termina en estado de aceptación.

Resumiendo, la máquina Diagonal está diseñada para tener la siguiente propiedad:

Diagonal para ante la entrada $w$ $\iff$ la máquina codificada en $w$ no para ante la entrada $w$.

Por último, tomaremos la codificación de la máquina Diagonal, y la aplicaremos como entrada a la propia máquina Diagonal. Como $w$ es la codificación de Diagonal, de lo anterior se sigue que Diagonal para ante sí misma como entrada si y solo si Diagonal no para ante sí misma como entrada. Esta conclusión es paradójica, pero todas las máquinas que hemos usado en la demostración, exceptuando Termina, son construibles; por lo tanto la clave de la demostración se encuentra, por reducción al absurdo, en la supuesta existencia de la máquina Termina. Al ser imposible la existencia de tal máquina Termina, que resolvía el problema de la parada, el problema de la parada no puede ser solucionado por ninguna máquina de Turing.

Véase también

• Constante de Chaitin

Referencias

• Sipser, Michael (2005). Introduction to the Theory of Computation (2 edición). Course Technology. ISBN 978-0534950972. 
• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-497777-7. 

• George S. Boolos, John P. Burgess & Richard C. Jeffrey (2007). Computability and Logic. Cambridge University Press. ISBN 978-0521701464. 

• Datos: Q622849