El problema de la parada
Antes de explorar el Problema de la Parada pensemos en una experiencia cotidiana. En ocasiones experimentamos esa sensación de algo que se nos escapa impidiéndonos dar con la solución a un problema. Sentimos que bastaría una pequeña epifanía, un «¡Eureka!», para que el problema quedase resuelto. De alguna manera, intuimos la cercanía de la solución aunque no la hayamos encontrado aún.
Funciones no computables
Esta experiencia no es formalizable en lenguaje matemático y por tanto, no es un procedimiento que podamos implementar algorítmicamente. Cuando operamos con algoritmos, no podemos establecer puntos intermedios entre «resuelto» y «no resuelto». O es una cosa o la otra.
Lo hemos reiterado repetidamente a lo largo de esta serie: la operación de una Máquina de Turing cualquiera debe detenerse en algún momento para considerarse efectiva. Si no hay parada, no puede haber una solución. En virtud de la equivalencia que hemos establecido entre función computable y Máquina de Turing, si una operación no nos devuelve un resultado, se considera que la función no es computable.
No es relevante si el output que ofrece la máquina es correcto o no. Eso dependerá de cómo su configuración se ajusta a nuestros conocimientos sobre el problema algorítmico en cuestión. Lo que buscamos es saber si tal procedimiento se para o no se para, es decir, si es computable.
Implementar una función no computable no es difícil. Una máquina que salte de una celda a otra jamás se detendrá ni nos dará respuesta alguna. Por ejemplo, para una máquina con las instrucciones siguientes:
Basta introducirle como input una cinta tal que:
y, si comienza en el estado Q_{0} por el lado derecho, saltará en bucle entre la primera y segunda celda. Recordar que Dj es 0 a la izquierda y 1 a la derecha. Aunque nuestra cinta tenga un signo para la parada, el cabezal jamás llegará a leerlo y nunca ejecutará dicha instrucción.
El Problema de la Parada
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.
Demostración
Esta demostración será algo pesada de ver pero le auguro un gran goce al lector cuando sea capaz de comprenderla. No por nada es uno de los mayores avances del siglo pasado en teoría de la computación. Así que pido una lectura sosegada.
Supongamos pues, que tal Máquina de Turing existiese. Llamémosla con el enigmático nombre de Z. A esta máquina le introducimos la descripción d_{T} de una máquina cualquiera T y su cinta m como hicímos con la Máquina Universal. Como estamos suponiendo que esta máquina existe y es capaz de resolver el problema, entonces la máquina debe parar el algún momento dándonos la respuesta a la pregunta: ¿T(m) se para? Tanto si T se para como si no, Z debe detenerse devolviéndonos un 1 si se para, y un 0 si no se para.
Si nuestra máquina es capaz de esto, será también capaz de responder a la pregunta: ¿ T(d_{T}) se para? Esto es, introducir a la máquina T su propia descripción como input en la cinta. Esto puede parecer raro. No nos preocupa la razón por la que alguien querría introducir como input de una Máquina de Turing su propia descripción. Lo que nos interesa es si tal cosa sea viable. Y efectivamente, mientras la descripción se encuentre escrita en un lenguaje entendible, una Máquina de Turing no tendría problemas en operar con dicho input. Para nuestra máquina Z esto sería así:
Vemos que la cinta de Z esta formada por dos secciones iguales. No nos resultaría difícil suponer que pudiese existir otra Máquina de Turing que operase a la manera en que haría Z, pero necesitando solo una de esas secciones d_{T}. Tal máquina, que llamaremos R, podría hacer un duplicado de d_{T} en la cinta.
Resultado final
R hace el mismo trabajo que Z: debe examinar la descripción de una máquina arbitraria T y detenerse diciéndonos si tal computación se para (1) o no (0). Podríamos modificar ligeramente a R de forma que, antes de detenerse, R ejecutara una ultima operación. Añadimos algún estado más a su configuración de manera que la máquina entre en bucle infinito en caso de que el resultado hubiera sido 1, T se para. Ya hemos visto arriba que configurar un bucle infinito es tarea sencilla.
En resumen: si Z existiera y resolviese la computabilidad de cualquier máquina T, sería viable construir un máquina R que se detuviese si T no se para, y que entrase en un bucle infinito si T se para. Y ahora viene el remate ¿Qué ocurre cuando R se enfrenta a su propia descripción? En vez de resolver la computabilidad de T introduciendo su descripción d_{T}, introduciríamos a R la suya propia d_{R}. En ese caso acabaríamos en una evidente contradicción absurda: R se detiene si R no se detiene, y R se detiene cuando R no se detiene.
La irresolubilidad del Problema de la Parada
Puede que la demostración que hemos perfilado resulte al lector artificiosa. Pero, bien examinada, nos daremos cuenta de que todos los pasos y operaciones que hemos realizado son legítimos y viables para un dispositivo como la Máquina de Turing. Todos menos el primero: suponer que pueda existir un Máquina capaz de resolver el procedimiento de decisión para una Máquina de Turing cualquiera.
El Turing original recurrió a una argumentación algo más refinada que la que aquí proponemos y puede que dediquemos a ella un artículo. Sin embargo, considero que esta es algo más intuitiva de ver y no nos obliga a introducir conceptos matemáticos auxiliares.
Cuando Turing propuso su máquina en 1936 era este el problema al que quería dar solución: los límites de lo consideramos un procedimiento mecánico. El resultado es equivalente en ciertos aspectos al obtenido por el matemático Kurt Gödel en 1931 cuando demostró con sus famosos Teoremas de Incompletitud las restricciones del formalismo lógico en las matemáticas. Recordemos que la Máquina de Turing es la expresión formal de lo que consideramos un procedimiento mecánico y que su poder computacional es el mayor de todos los autómatas. Aun así, Turing descubrió puntos flacos: tipos de problemas irresolubles para un algoritmo.
Lo que no es el Problema de la Parada
Debe quedar claro algunas cosas que pueden prestar a confusión. La irresolubilidad del Problema de la Parada significa que siempre existirá la posibilidad de que un programa ejecutado se quede colgado en un bucle infinito. Es perfectamente posible diseñar un Procedimiento de Decisión computable y automático que reconozca cuando algunos programas nunca van a llegar a pararse. Pero lo que no es posible es que sea capaz de resolver esta cuestión para cualquier programa.
Otra cosa que puede llegar a confundir es que, en ocasiones, en base a la demostración que hemos propuesto, algunos pueden llegar a pensar que es al mostrarle al ordenador su propia descripción como input cuando este queda colgado. Esto es falso. La demostración de Turing afirma que siempre existirá alguna instrucción que no pueda ser decidible para un algoritmo que resuelva la computabilidad de un procedimiento mecánico. Pero en ningún momento la demostración nos indica qué instrucciones o que input en concreto se resistirán a dicho algoritmo. Solo demuestra que siempre habrá alguno. El problema de cuántos de esos programas indecibles existen lo veremos cuando exploremos el Teorema de Rice.
El problema de la Mente
Las implicaciones del Problema de la Parada en la teoría de la mente es un tema a debate desde hace un siglo. Los seremos humanos podemos intuir el infinito sin tener que caer irremediablemente en bucles interminables. De alguna manera, nuestra cognición nos permite tomar distancia cuando llevamos a cabo una operación mecánica, permitiéndonos «salir» del bucle cuando atisbamos que se repite sin llevarnos a ningún lado. ¿Cómo es que nuestro cerebro no se «cuelga» como lo haría una Máquina de Turing?
Esta pregunta puede parecer ingenua. Comparar el cerebro con la «estúpida» máquina de Turing parece casi blasfemo. Pero recordemos que la Máquina de Turing es el dispositivo de mayor poder computacional, equivalente a cualquier procedimiento algorítmico. Además la demostración de arriba es generalizable a un Máquina de Turing por compleja que esta sea. Si nuestro cerebro fuese algún tipo de dispositivo mecánico, por miles o miles de millones de estados y signos que este fuese capaz de operar, se encontraría restringido por las mismas limitaciones que un Máquina de Turing.
Nos vemos ante dos posibles salidas ante este entuerto: o bien existe algo en nuestro cerebro que le hace superior a una Máquina de Turing, o bien deberíamos desechar la idea de que la Máquina de Turing sea el dispositivo computacional definitivo. Puede que los nuevos avances en computación neuronal nos demuestren que ambas opciones son en realidad la misma.
Desarrollar las implicaciones del Problema de la Parada, así como de los Teoremas de Incompletitud de Gödel, será tarea de este portal en artículos posteriores.
Lecturas Recomendadas
– Minsky, M. (1967) Computation. Finite and Infinite Machines.
