TIPOS DE MAQUINA DE TURING

EL PROBLEMA DE LA PARADA (HALTING PROBLEM)

EL PROBLEMA DE PARADA CONSISTE EN :

Dada una Máquina de Turing M y una palabra w, determinar si M se detendrá 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.

RELEVANCIA 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: Dado un programa p y sus datos de entrada x, decidir si p eventualmente terminará en un número finito de pasos o si entrará a un bucle infinito.Esta pregunta es, en términos modernos, el problema de la parada. Una forma muy natural de intentar resolver el problema es hacer funcionar el programa p con los datos de entrada x y esperar para ver si termina; sin embargo habría que determinar cuánto tiempo hay que esperar para estar completamente seguros de que p en verdad nunca termina. De hecho, esto es imposible: está demostrado que este problema no se puede solucionar algorítmicamente –es decir, que es irresoluble.

El ejemplo que hemos propuesto es sencillo. Desde la perspectiva humana es evidente que una operación así nos sumerge en un bucle que nunca terminará. Pero…¿Es evidente para una máquina?  ¿Podemos usar una máquina para saber cuando estas instrucciones terminan en un bucle infinito? En otras palabras… ¿Es en sí un problema computable resolver si una máquina y su cinta es o no computable?

Necesitamos un conjunto de instrucciones mecánicas que nos permitirán decidir si una Máquina de Turing y su cinta es o no una función computable. Hemos visto en el artículo anterior como describir una Máquina de Turing arbitraria de forma que sea «comprendida» por otra Máquina de Turing, la máquina 

$U$

El Problema de la Parada se pregunta si, introduciendo una descripción en la cinta como input, existirá un Máquina de Turing que nos diga si esa descripción y su cinta es una función computable o no. Dicho de otra manera, nos preguntamos si existe un Máquina de Turing capaz de resolver la parada para cualquier máquina. Aunque explorar esta cuestión será el objetivo de este artículo iré adelantando la respuesta: no, no existe Máquina de Turing capaz de hacer tal cosa.

Para demostrar su imposibilidad usaremos un método bien conocido en el ámbito matemático: la reducción al absurdo. Para argumentar que algo no existe, basta con mostrar como su existencia nos obligaría a afirmar contradicciones absurdas. Por lo tanto, tal cosa no puede existir.