Helting problem

HALTING PROBLEM

Detener problema
Introducción
El problema de la parada es un problema de decisión acerca de las propiedades de los programas de computadora en un fijo de Turing-completomodelo de computación, es decir, todos los programas que se pueden escribir en algún determinado lenguaje de programación que es lo suficientemente general como para ser equivalente a una máquina deTuring. El problema consiste en determinar, dado un programa y una entrada al programa, si el programa con el tiempo se detiene cuando se ejecuta con esa entrada. En este marco abstracto, no haylimitaciones de recursos en la cantidad de memoria o el tiempo necesario para la ejecución del programa, sino que puede tomar arbitrariamente larga, y el uso de espacio de almacenamiento arbitrariamentemucho, antes de detener. La pregunta es simplemente si el programa dado jamás se detiene ante una entrada particular.

En teoría de la computabilidad , el problema de la parada se puede afirmar losiguiente: Teniendo en cuenta la descripción de un programa de computadora , debe decidir si el programa termina de ejecutarse o continúa funcionando para siempre. Esto es equivalente al problema dedecidir, teniendo en cuenta un programa y una entrada, si el programa con el tiempo se detiene cuando se ejecuta con esa entrada, o puede funcionar para siempre.
Alan Turing demostró en 1936 que ungeneral algoritmo para resolver el problema de la parada para todo programa de pares de entrada-posible, no puede existir. Una parte clave de la prueba era una definición matemática de un ordenador y elprograma, lo que se conoce como una máquina de Turing .
Formalización del problema de la parada
En su prueba original de Turing formalizó el concepto de algoritmo mediante la introducción demáquinas de Turing . Sin embargo, el resultado es de ninguna manera específica a, sino que se aplica por igual a cualquier otro modelo de computación que es equivalente en su potencia de cálculo a las...