Problema de la parada

terminará en un número finito de pasos cuando es ejecutada usandoEn 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: Conocer si existe el programa P es, en términos resumidos, el problema de la parada.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.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ó.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: 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).En lenguaje Python: Resumiendo, el programa Diagonal está diseñado para tener la siguiente propiedad (entiéndase la flecha como «siempre y cuando»):Como w puede ser el código de cualquier programa, particularmente puede ser el del mismo Diagonal: En este caso se tieneComo 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.es la codificación de la cadena que se le alimenta ae r m i n a, 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 cualquieraAhora crearemos una máquina Diagonal que recibe de entrada una cadenaPrimero Diagonal utilizará la máquina Copia para duplicar la cadenaA continuación, Diagonal pasará este resultado a través de Termina para decidir si la máquina representada pory 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.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.