Problema De La Parada

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ó queel problema de la parada de la Máquina de Turing es indecidible, 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ónserí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 embargohay 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 existala 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álisisde 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 argumentoen 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 deCantor). 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 se pueden suministrarse a sí mismos como dato de entrada). A continuación, Diagonal hace lo opuesto: Si w terminaentonces 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...