El problema de la decidibilidad. Alan M. Turing III

Vídeo explicando la Máquina de Turing

En esta tercera entrega sobre la obra de Alan Turing, veremos la aportación más importante del mismo al campo de la Ciencia de la Computación, y la que hace que sea considerado por ello como el padre de la Informática, que es su introducción del concepto de la Máquina de Turing, que podemos considerar como la definición matemática de lo que es un algoritmo.

Desde siempre, pero fundamentalmente desde que Galileo hiciera notar que las leyes naturales podían describirse gracias a las matemáticas, se había dado por supuesto que todo problema enunciado en términos matemáticos, más tarde o más temprano, podría resolverse siguiendo una serie de pasos estipulados, ya fuese en forma geométrica, el método más usual para los antiguos griegos, o mecanismos de tipo más algebraico, a los cuales estamos más habituados en la actualidad.

Sin embargo, el hecho de que esto se diera por sentado no significaba que necesariamente debiera ser así, por lo que se planteaba el despejar cualquier duda de ello. De ahí que se planteara el que se denominó como «Entscheidungsproblem» o problema de la decisión, inicialmente planteado ya por Leibniz en el siglo XVII, el cual, tras  construir su máquina mecánica de cálculo, soñaba con construir otra máquina que pudiera manipular símbolos para determinar si una sentencia matemática es un teorema, e incluso que pudiera llegar a reducir la filosofía al cálculo. Este problema fue formalizado por David Hilbert, primero parcialmente, a través de su décimo problema de la Conferencia de París, y ya en forma más elaborada en el VIII Congreso Internacional de Matemáticas, celebrado en Bolonia en 1928, ya casi al final de su vida. Para Hilbert era crucial que todo problema dispusiera de una solución exacta, cuya única dificultad rayara simplemente en encontrarla, pero sobre cuya existencia no cupiera dudas. Y así lo plasma en una de sus reflexiones:

“Todo problema matemático definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debido a la constatación de la imposibilidad de resolverlo, a lo que se debería la falla necesaria de todos los intentos. Una de las cosas que más nos atrae cuando nos dedicamos a un problema matemático es precisamente a que dentro de nosotros siempre escuchamos la llamada: He aquí el problema, busca la solución; puedes encontrarla por pensamiento puro, ya que en matemáticas no existe cosa alguna que no pueda conocerse”.

Así pues, en dicho congreso, Hilbert planteó, nada más y nada menos, la búsqueda de un procedimiento algorítmico general válido para resolver todas las posibles cuestiones matemáticas. Esta cuestión encajaba en su programa formalista, puesto que su mayor interés era situar las matemáticas sobre una base inatacable, con axiomas y reglas que quedaran establecidas de una vez por todas. En definitiva, su planteamiento del problema era obtener la respuesta a tres importantes preguntas:

1. ¿Son las matemáticas completas, es decir cualquier proposición puede ser probada o rechazada?
2. ¿Son las matemáticas consistentes, es decir no es posible demostrar algo falso?
3. ¿Son las matemáticas decidibles, es decir cualquier proposición se puede demostrar como cierta o falsa tras una secuencia finita de pasos?”

Al plantearlo, la idea previa de Hilbert era que la respuesta sería afirmativa para estas tres cuestiones. No es para menos, teniendo en cuenta las palabras que ordenó grabar sobre su tumba en Gotinga: «Wir müssen wissen. Wir werden wissen«, »Debemos saber y sabremos’,’ que muestran su rechazo categórico al entonces vigente «Ignoramus et ignorabimus«.

Sin embargo, poco después de este congreso, en 1930, Kurt Gödel demostró, por medio de sus célebres Teoremas de Incompletitud que las dos primeras preguntas no pueden ser ciertas a la vez para la teoría de los números. El primer teorema de Gödel afirma: “En cualquier formalización consistente de las matemáticas que sea lo bastante fuerte para definir el concepto de los números naturales, se puede construir una afirmación que ni se puede demostrar ni se puede refutar dentro de ese sistema”, mientras que el segundo afirma: “Ningún sistema consistente se puede usar para demostrarse a sí mismo”.

Esto supuso un auténtico mazazo para las matemáticas, pues eso significa, en palabras llanas, que si queremos saber la verdad, y nada más que la verdad, no podremos saber toda la verdad. La verdad absoluta no existe, ni siquiera en un ámbito como el de las matemáticas.

Sin embargo, aún quedaba la tercera pregunta. Todavía se podían salvar los muebles, en el sentido de que podríamos clasificar las sentencias matemáticas en tres grupos en lugar de dos, que serían las que son ciertas, las que son falsas y, por último, las que no sabemos ubicar. Evidentemente, no es lo mismo, pero es lo que había. Para ello, sólo deberíamos saber encontrar a qué grupo pertenece una proposición dada. Pero de nuevo, las cosas no salieron como se esperaba.

La dificultad de resolver esta última cuestión estribaba, fundamentalmente, en la inexistencia de una definición precisa de lo que se debe entender por un «procedimiento mecánico» para realizar cálculos. Y es Turing quien lo establece en 1936 en su trabajo “On computable numbers” introduciendo el concepto de Máquina de Turing, como concepto adecuado de procedimiento  mecánico, y a partir de él, el de Máquina Universal de Turing, como idea de lo que es un computador programable que ejecuta dichos procedimientos.

La idea de Máquina de Turing, en esencia, no es complicada, y consiste en un dispositivo abstracto dotado de una cinta de memoria ilimitada, formada por celdas consecutivas donde se pueden leer y escribir símbolos. Aún cuando hay infinitas celdas posibles, en cualquier instante hay en uso sólo una cantidad finita de ellas, estando todas los demás en blanco. Además, en dicha cinta existe un cabezal que puede estar en diferentes estados posibles.  Finalmente, su funcionamiento es como sigue; en cada paso de su ejecución, en primer lugar, el cabezal lee la posición en la que se encuentra en la cinta, y dependiendo del estado en el que esté, escribe en consecuencia; tras lo cual avanza o retrocede a la celda adyacente. Por último, puede cambiar de estado, y así continúa hasta el momento en que no tiene definida una tarea por hacer. Con la ayuda de esta máquina infernal Turing demostró que la respuesta a la tercera pregunta era un rotundo NO. Su tesis vino a demostrar que las matemáticas eran un montaje intelectual con la misma envergadura metafísica que puede tener el juego del ajedrez.

El problema para el que encontró que no había una solución algorítmica era el que, desde entonces, se conoce como problema de parada (Halting Problem). Es un problema también sencillo de entender, que consiste en determinar si un determinado programa parará alguna vez o tendrá una ejecución indefinida. En lugar de usar las Máquinas de Turing, veamos un ejemplo en un lenguaje de programación informal. Para ello supongamos este sencillo programa:

I = 0;
Mientras  I  < 10  Repetir I := I + 1;

Es un bucle correcto y bien estructurado que finalizará tras diez pasos de ejecución. Pero es fácil cometer un error al escribirlo, y poner en su lugar esta otra versión:

I = 0;
Mientras  1  < 10  Repetir I := I + 1;

Confundir los símbolos «1» e «I» no es nada difícil, y el resultado de este cambio es que, en la pregunta, 1 siempre es menor que 10, por lo que el programa escrito así nunca podrá salir del bucle, ya que la condición siempre será cierta. Así pues, nos podemos plantear una pregunta de indudable interés ¿Puede existir un método para saber si un programa escrito en un determinado lenguaje de programación parará? Y ello, por supuesto, sin necesidad de ejecutarlo, sino por inspección de su código. Si existiera nos permitiría encontrar diferencias como las que existen en los dos ejemplos anteriores, lo que sería tremendamente útil.

Pues bien, no existe, y el ingenioso razonamiento de Turing para mostrarlo fue el siguiente. Supongamos que dicho método existe. Si es así, entonces será programable y existirá, por tanto, un programa, que denominaremos P, y que hará lo siguiente:

Programa P

Acepta como entrada el código de un programa X

Analiza el código de X

Si el programa X se detiene en cualquier circunstancia Entonces responde «SI»

Si existe una posibilidad de que X nunca detenga su ejecución Entonces responde «NO»

A priori no parece complicado, y no hay razón para suponer que ese programa no pudiera existir. Ahora bien, el razonamiento al que llegó Turing es el siguiente. Si disponemos de dicho programa P, podemos entonces construir, a partir de él, otro programa diferente R, que responderá al siguiente comportamiento:

Programa R

Ejecutar el programa P tomando como entrada el programa R

Si la salida es «SI» Entonces ejecutar un bucle indefinido

Si la salida es «NO» Entonces finalizar.

Y ahora viene lo mejor, pues nos podemos preguntar ¿Parará siempre el programa R tal y como lo hemos diseñado, o existirá alguna posibilidad de que tenga una ejecución infinita? Para saberlo, qué mejor que recurrir a chequearlo con el programa P que, hemos supuesto, siempre nos responderá a esta cuestión y para eso sirve. Y así, tenemos dos posibilidades, que nos responda «SI» o «NO», no cabe ninguna otra. Pero entonces:

•  Si la respuesta es «SI», significa que R siempre se detendrá, en cualquier circunstancia. Ahora bien, tal y como está definido R, tenemos que dicha respuesta «SI» ocasiona que R no puede detenerse. Tenemos una contradicción inasumible.

• Si la respuesta es «NO», significa que R puede no detenerse. No obstante, por la construcción del propio R, eso significa que SIEMPRE finalizará su ejecución. También tenemos una contradicción.

Así pues, estás perdido Flánagan, en ambas circunstancias tenemos sendas contradicciones que nos llevan a que dicho programa, simplemente no puede existir.

Este fue el primer caso de problema indecidible que la genial visión de Alan Turing nos mostró en su artículo que haría historia, aparte de definirnos cómo debería ser un computador, y eso antes de que existiesen. Como curiosidad, indicar que en el primer envío del mismo, fue rechazado con el curioso argumento de que su máquina ni existía ni podía existir.

Para finalizar, simplemente comentar que el problema de la incompletitud, como ya he señalado en la primera entrada relativa a la magna obra de Alan Turing, ha sido utilizado en repetidas ocasiones como argumento en contra de que pueda existir una consciencia presente en una máquina, a lo que ya objetó el propio Turing que esa limitación también aplica en seres humanos. No sólo eso, sino que podríamos argumentar que incluso aplica a un hipotético Ser Omnipotente, como ya señalé en tono lúdico hace algunos años, pues incluso con toda su omnipotencia no podría proporcionarnos algo tan sencillo como un programa que decidiera si otro programa pararía o no.

Fernando Cuartero

Relacionadas

• ¿Pueden pensar las máquinas? Alan M. Turing I
• Bletchley Park y la máquina Enigma. Alan M. Turing II

fcuartero