Los números computables, la máquina Enigma y Alan Mathison Turing

 

 alanturing

 

A mediados del Siglo XX, en el año 1936, un genio matemático llamado Alan Mathison Turing publicó un artículo de investigación que revolucionóel mundo de la lógica matemática. A principios de siglo, otro matemático llamado David Hilbert planteó un conjunto de 23 problemas no resueltos por aquel entonces, de vital trascendencia para la disciplina matemática, a la espera de que algunas personas los resolvieran. Hilbert tenía una concepción optimista de las matemáticas, y creía que todo podía ser solucionado, tenía una gran confianza en el poder de esta herramienta.

Uno de los problemas que Hilbert planteó, conocido como Entscheidungsproblem, fue el problema de la decisión. El problema de la decisión consiste en averiguar si existe un algoritmo genérico que decida si una fórmula lógica de primer orden (o lo que es lo mismo, una expresión lógica que empieza con los cuantificadores “para todo” o “existe”) es un teorema o no lo es. En su artículo “Números computables”, publicado por Turing en 1936 se resuelve esta cuestión, llegándose a la afirmación de que tal algoritmo genérico no existe.

Turing utilizó dos demostraciones para lanzar tal afirmación. El artículo de los números computables, que yo mismo he leído, es de suprema originalidad y elegancia, un tipo de originalidad que le da el carácter simplemente de genial.

Para llegar a sus conclusiones, Turing parte de unas máquinas hipotéticas, que en su honor se llamarían después “máquinas de Turing”, y cuyo comportamiento viene a ser parecido al de un automáta o sistema de control secuencial.

Una máquina de Turing es un dispositivo ideal que en cada momento sólo lee el contenido de una única casilla de una cinta de papel que se prolonga enambas direcciones. En función del contenido de la casilla sobre la que está situada y de la configuración interna (lo que sería el estado del autómata), lamáquina realiza alguna operación como desplazarse una casilla a la izquierda, o borrar el contenido de la casilla o escribir un símbolo sobre la misma, y además su configuración bascula a otro estado interno. Se trata pues de un dispositivo secuencial, que opera en base a las secuencias de valores de entrada y de estados de configuración.

Turing también definió lo que ahora se conoce como “máquina de Turing universal”, que es un tipo de máquina que recibe la descripción del comportamiento de una máquina cualquiera de Turing y que reproduce su comportamiento. Tal descripción lo recibe como una secuencia de números de entrada que se denominan  “número de descripción” o “descripción estándar” de la máquina. Una vez introducido este número en una máquina de Turing universal ésta imita la máquina de Turing cuyo número de descripción es el introducido. Esta máquina universal vendría a ser como un ordenador con un programa en ejecución, pues es capaz de ejecutar un algoritmo que le pasemos como parámetro.

Además, el autor de “números computables” distinguió entre máquinas que funcionan sin circularidad y máquinas que funcionan con circularidad. El segundo de estos tipos no es deseable para una máquina de Turing pues significaría que el algoritmo que hemos programado en ella con la tabla de configuración (o con el número de descripción) no llega a pararse nunca, sino que vuelve infinitas veces a operar del mismo modo según el programa, y por tanto dicho algoritmo no genera un resultado.

Si Turing teorizó en base a estas idealizaciones y abstracciones de máquinas de Turing, y máquinas libres de circularidad, lo hizo porque cualquier fórmula lógica de primer orden tiene un equivalente numérico en base a ciertas reglas, algo similar a lo que había hecho Kurt Gödel en su artículo sobre incompletitud, lo que se conoce como Gödelización. En base a ciertas premisas, se puede conseguir el equivalente a cualquier fórmula lógica de forma biyectiva, esto es, uno a uno, y así, según esta forma de razonar, una demostración no será otra cosa que una secuencia de números en cierto orden. De aquí viene el uso de máquinas de Turing, pues si una máquina de Turing obtiene una secuencia de números computables siguientes a la entrada, en lacual se codifican las premisas de la demostración, y al final se para, ello significará que de las premisas se llega a la conclusión, y que ésta es un teorema.

La primera de las demostraciones del teorema se basa en lo siguiente : supongamos que existe un procedimiento que decide si una máquina de Turing se va a parar (no tiene circularidad).
Supongamos que hacemos una lista con todas las secuencias posibles de números que proporciona la máquina de Turing ante números de entrada crecientes para un algoritmo (o máquina de Turing) fijo, que no presente circularidad, cosa que podemos hacer dado el supuesto de la existencia de la máquina que decide sobre la parada. Supongamos que esta lista la ampliamos para todas las máquinas de Turing posibles con parada, cada una con la lista de secuencias de números computados. Si ahora empleamos un razonamiento de diagonalización al estilo de Cantor se obtiene lo siguiente: 

Tomamos el primer elemento de la primera secuencia de la lista y le incrementamos uno, tomamos el segundo elemento de la segunda lista y le incrementamos en uno, tomamos el  tercero de la tercera lista y lo aumentamos uno,… tomamos el N-ésimo -para cualquier N- de la N-ésima lista y lo incrementamos en uno…. Así llegamos a una secuencia que es computable, pero que no figura en la lista de todas las posibles secuencias computables, pues el proceso de extraer los números de la diagonal y de incrementarlos en uno es programable en una máquina de Turing,pero no figura esta nueva secuencia en la lista original. Por tanto hemos llegado a unacontradicción y el supuesto de la existencia del algoritmo de decision es falsa.

La segunda de las demostraciones es totalmente diferente : supongamos que existe el algoritmo que decide sobre la parada o no de una máquina cualquiera T (ausencia o no de circularidad). Supongamos que conectamos esta máquina D de decisión a una máquina de Turing universal U. El funcionamiento de DU consiste en que a D le pasamos el número de descripción de la máquina o algoritmo cuya parada queremos testear, en caso de decidir que es circular el funcionamiento termina ahí y no hay salida, en caso de no circularidad la máquina D le pasa a la máquina U el número de descripción para que imite la máquina T. La máquina DU así construida es una máquina de Turing libre de circularidad pues solo da una secuencia finita de salida en el caso de que el algoritmo D cuya existencia suponemos decida que la máquina T no es circular, y en caso de ser circular también da una secuencia de salida finita (secuencia vacía). Ahora bien, supongamos que a la propia máquina DU le introduzcamos el número de descripción de esa misma máquina DU, el cual existe, por ser DU máquina de Turing. ¿Qué pasará?. Pues pasará que DU verificará que DU no es circular, cosa que suponemos, y a continuación la imitará tomando el número de descripción de DU y viendo que ésta no es circular, con lo cual le pasará el número de descripción de DU de  nuevo a sí misma, y así indefinidamente, con lo cual la máquina DU es circular lo cual contradice la hipótesis de no circularidad de DU y por tanto de la existencia de la máquina D.

Por tanto, no existe un algoritmo genérico que determine si una máquina de Turing cualquiera y por tanto un algoritmo parará, con lo cual en principio no tenemos forma de saber si una fórmula de lógica de primer orden, traducidos sus símbolos a números, tiene demostración o no (es o no un teorema y por tanto constituye una verdad o no).

 

enigma

 

Alan Turing fundó las bases de la informática y junto a un equipo de investigadores creó uno de los primeros ordenadores de la historia, el “Colossus”. Además de esto y de sus contribuciones a la lógica matemática, este hombre fue figura clave en la desencriptación de los mensajes codificados por los alemanes mediante la máquina Enigma.

La máquina Enigma brindaba un sistema de encriptación polialfabético con muchísimos alfabetos de sustitución, uno por cada avance del rotor de la máquina, con lo cual para determinar el mensaje cifrado habría que conocer con exactitud los parámetros involucrados en la puesta en marcha de “Enigma”, esto es, la posición de los rotores y de las clavijas. Esto daba un número de combinaciones descomunal, por lo que Enigma era un sistema muy robusto y difícil de desencriptar. El sistema Enigma viene a ser una evolución del cifrado Vigènere, que es también polialfabético, pero que tiene un número de alfabetos diferentes para codificar cada mensaje solamente igual al número de letras de la palabra clave. Enigma tenía una “letra de palabra clave” por cada posicion de los rodillos.

Por su importante contribución al descifrado de los mensajes Enigma, Turing fue condecorado con la Orden del Imperio Británico.

La muerte de Turing fue prematura y triste. Al parecer se suicidó comiendo una manzana envenenada con cianuro, pues en un juicio por robo en su casa tuvo que confesar que era homosexual, y entonces esto estaba penado por la jurisdicción británica. En otras palabras, le hicieron la vida imposible. Pero su obra nos ha quedado intacta, para el goce de las generaciones presentes y venideras.

 

 

~ por verpiman en Septiembre 9, 2009.

Deja un comentario