A mediados del Siglo XX, en el año 1936, un 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 de nombre 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 demostrado, tenía una gran confianza en el poder de esta rama del conocimiento.
Aunque Hilbert no lo incluyó en su lista de problemas de 1900, veintiocho años más tarde otra conferencia de Hilbert hizo trascender otro desafío a las matemáticas modernas, conocido como Entscheidungsproblem, esto es, el problema de la decisión. El problema de la decisión consiste en su planteamiento más general en averiguar si existe un algoritmo genérico que decida si un problema matemático tiene o no demostración. En el planteamiento de Turing, éste lo particularizó, indagando acerca de si existe un procedimiento efectivo con el que se pueda averiguar si una fórmula del cálculo funcional es un teorema o no lo es. En su artículo “Sobre los números computables, con una aplicación al Entscheidungsproblem”, 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, consiguiendo un artículo de una gran belleza, originalidad y elegancia.
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 en ambas 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), la máquina bascula hacia otro estado distinto, y después de ésto, realiza alguna operación dependiente del estado, como desplazarse una casilla a la izquierda, o borrar el contenido de la casilla o escribir un símbolo sobre la misma. 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 de Turing cualquiera y que reproduce su comportamiento. Tal descripción la 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 mediante el “programa”. Y una máquina de Turing no universal es en realidad lo equivalente a un programa informático o a un sistema electrónico digital secuencial.
Además, el autor del artículo que aquí describo, 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 las fórmulas del cálculo funcional tienen un equivalente numérico en base a ciertas reglas, algo similar a lo que hizo Kurt Gödel a las fórmulas lógicas de primer orden en su artículo sobre incompletitud, lo que en dicho contexto se conoce como Gödelización. En base a ciertas premisas, se puede conseguir el equivalente a cualquier fórmula 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, en cuya génesis intervienen las reglas mencionadas, y que siguen a la entrada, en la cual se codifican las premisas de la demostración, y al final se para en el número equivalente a una cierta proposición, éllo significará que de cierta premisa se llega a cierta 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 finitas 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 lo incrementamos en uno, tomamos el segundo elemento de la segunda lista y lo incrementamos en uno, tomamos el tercero de la tercera lista y lo aumentamos en uno,… tomamos el N-ésimo, para cualquier N, de la N-ésima lista y lo incrementamos la unidad…. Así llegamos a una secuencia que es computable, pero que no figura en la lista de todas las posibles secuencias computables. Es computable, puesto que el proceso de extraer los números de la diagonal y de incrementarlos en uno, a partir de una lista de secuencias computables, es programable en una máquina de Turing. Bastaría con conectar los resultados de todas las máquinas que generan todas las secuencias computables, trabajando en paralelo, a una máquina que es secuencial y por tanto de Turing. Con los actuales diseños electrónicos digitales, esta máquina se podría construir con un demultiplexor de las secuencias computadas, a cuyas líneas de selección de canal de entrada se les aplica un contador, seguido de un sistema combinacional que suma la unidad al número situado a su entrada. Se deduce entonces que el algoritmo o máquina de Turing que obtiene la susodicha secuencia es una operativa computable, pero al no figurar esta nueva secuencia en la lista original que supuestamente contenía todas las secuencias computables posibles, se llega a una contradicción, y el supuesto de la existencia del algoritmo de decisión es falso.
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 T, equivalente al 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 proporciona a la máquina universal 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 sólo 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 introducimos 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, una secuencia lógica de razonamientos, terminará su evolución en un resultado. De esta manera, en principio no tenemos forma de saber si una fórmula del cálculo funcional, traducidos sus símbolos a números, tiene demostración o no. (No sabemos de antemano si es o no un teorema, con lo cual ignoramos su naturaleza en cuanto a verdad o falsedad). Ésto implica que también podríamos extender este resultado a un problema matemático genérico, dado que hemos encontrado un contraejemplo que niega ya por sí mismo el enunciado “existe un algoritmo que decide si cualquiera enunciado tiene demostración”, aunque la prueba de Turing relativa al EintschengdungProblem estaba específicamente parcelada a las fórmulas del cálculo funcional. No obstante, en su trabajo hace una descripción muy pormenorizada del funcionamiento de las máquinas de Turing y del concepto de número computable, entendido como aquél que puede ser obtenido mediante cómputo en un número finito de pasos.
Alan Turing fue por lo tanto el principal fundador de las bases teóricas de la informática (quizás su principal aportación fue el concepto de computador de programa almacenado en memoria), aunque no debemos olvidar que se debe a John Von Neumann la primera descripción pormenorizada de la arquitectura de computadores que lleva su nombre y que aún hoy se utiliza, y que Claude Shannon desarrolló la teoría matemática de la información, ambos coetáneos suyos. Junto a un equipo de investigadores liderado por el ingeniero británico Tommy Flowers, Turing creó uno de los primeros ordenadores de la historia, el “Colossus”, que en realidad no era un computador de propósito general o máquina de Turing universal. El objetivo de “Colossus” era descifrar los mensajes de comunicaciones emitidos por los nazis, ya avanzada la II Guerra Mundial, encriptados con la máquina “Tunny”, creada por la empresa alemana Lorentz. Esta máquina operaba en código binario y alimentaba con un chorro de bits un teletipo. Dicho flujo transmitido se obtenía a partir de dos sumas binarias sucesivas del chorro original o mensaje en claro pasado al código binario, con dos claves binarias obtenidas mediante el concurso de 12 rotores mecánicos, que se emitía con el teletipo y su propia idiosincrasia de señales. Estos mensajes eran de vital importancia, dado que Tunny era utilizada para las comunicaciones del Alto Mando Alemán. Además de la creación de Colossus y de sus contribuciones a la lógica matemática, Turing fue figura clave en la desencriptación de los mensajes codificados por los alemanes mediante la máquina Enigma, gracias a su diseño y puesta a punto de las máquinas bomba que se usaban para agilizar el descifrado de Enigma. En realidad las máquinas bomba no fueron un invento original del protagonista de esta entrada, ya que que en los primeros embites de la guerra, otro grupo de matemáticos y criptógrafos polacos liderados por el matemático Marian Rejewski construyeron máquinas bomba para agilizar la rotura del código Enigma original. Sus desarrollos fueron comunicados a las inteligencias francesa y británica. Pero los nazis perfeccionaron a base de otros añadidos la codificación Enigma original. Por ello los criptógrafos de Bletchley Park, lugar donde se libró la verdadera guerra contra Enigma y donde Alan Turing trabajó, se vieron sumidos en la total oscuridad en lo que al desciframiento se refiere. Bletchley Park está situado a unos 80 km al Norte de Londres, y allí se construyó un complejo de barracones junto a una mansión victoriana ya existente, utilizándose para las operaciones de la escuela gubernamental de códigos y cifrado (GC&CS), entidad vinculada al servicio secreto británico. La figura de Turing en este lugar fue realmente muy importante, ya que rediseñó las máquinas bomba gracias a los “pellizcos” que los aliados obtuvieron consiguiendo máquinas Enigma y documentación de U-boats capturados, y gracias a su portentosa inteligencia. La existencia del complejo de Bletchley Park fue el secreto mejor guardado de los aliados, y todo lo relacionado con él no fue desclasificado hasta muchos años más tarde del final de la guerra. De hecho, Winston Churchill, primer ministro británico a la sazón, y que fue una de las contadas personas que tenía conocimiento de que se estaban descifrando los mensajes, (que los alemanes consideraban, no sin justificación, indescifrables) en sus círculos más privados designaba a Bletchley Park como “mi oca de los huevos de oro que nunca cacarea”. Una vez terminada la II Gran Guerra, Alan M. Turing llevó a cabo diversas investigaciones pioneras en la biología matemática, relacionadas con la morfogenésis, y en el campo de la inteligencia artificial (a la que aportó los fundamentos y algunos conceptos como el que se conoce como “test de Turing”), usando para ello los primeros computadores que se estaban creando en Gran Bretaña.
Pero tal vez la hazaña de Turing que tuvo más trascendencia práctica -aunque desde luego no fue su mayor logro hablando en términos generales- fue romper el código Enigma de los submarinos nazis, conocido en Bletchley Park como “Shark”. Gracias a ello los convoyes de buques mercantes que viajaban desde Estados Unidos transportando suministros, pudieron ser salvaguardados, después de un gran número de bajas, evitándose la derrota británica en el momento crucial posterior a los bombardeos sobre Inglaterra, cuando Francia ya estaba ocupada por el ejército nazi.
La máquina Enigma brindaba un sistema de encriptación polialfabético con muchísimos alfabetos de sustitución, uno por cada avance de los rotores 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, y por supuesto poseer una Enigma idéntica a la “transmisora”. Un análisis de frecuencias complejo no bastaba para descifrar un mensaje, dado que aún a pesar de que el mensaje transmitido fuese largo, los alfabetos de sustitución se sucedían al pulsar cada tecla y no llegaban a repetirse.
Enigma tenía la apariencia de una máquina de escribir, estaba alimentada por una pila, y su funcionamiento se basaba en cerrar circuitos de corriente continua. Cuando ésto ocurría, es decir, al pulsar cada tecla, la corriente fluía desde el teclado, pasando hacia el panel “stecker” o clavijero, que era configurable, y de éste iba al tambor de entrada, que estaba en contacto con el primer rotor. Cada rotor tenía dos superficies planas a ambos lados y 26 dientes, correspondientes a las 26 letras del alfabeto. Existían hasta cinco rotores con distintos cableados. En cada uno de esos rotores había un cableado diferente entre la interfaz de entrada, que una vez colocado contactaría con el rotor anterior (con el tambor de entrada para el primero de ellos), y su interfaz de salida (que ya posicionado estaba en contacto con el rotor siguiente). Después de la cara de salida del último rotor había un reflector, con el que se conseguía que, a igual configuración de la máquina, una letra del teclado fuese la misma que la letra iluminada en el panel luminoso obtenida por la pulsación de su traspuesta, es decir que Enigma sirviera tanto para cifrar como para descifrar si se usaba la misma clave. Desde el reflector la corriente seguía fluyendo por los rotores en sentido inverso al anterior, pero siguiendo otros caminos eléctricos diferentes; y de nuevo a través del clavijero pasando por otra clavija distinta, y de ahí a un terminal de la bombilla de la letra cifrada (o descifrada según el extremo de comunicaciones en que se operase). Como el otro terminal de cada bombilla estaba conectado con uno de los terminales de cada pulsador, al pulsar sobre él se cerraba el circuito y se obraba el milagro, produciéndose además un avance de una letra del rotor de menos peso, que podía acarrear un avance del rotor siguiente al terminarse una vuelta completa del mismo. Esto mismo ocurría con el segundo rotor y sucesivos, y así hasta las 26 x 26 x 26 pulsaciones en la máquina de 3 rotores, momento en que se volvía a tener la misma configuración de rotores que en la primera letra codificada y por tanto el mismo alfabeto de sustitución. Una letra nunca se codificaba en dos pulsaciones consecutivas con la misma letra cifrada, y asimismo una letra jamás se codificaba igual a sí misma, lo cual brindó a los criptógrafos de Bletchley Park un medio para obtener plantillas de letras posibles en un mensaje, constituyendo uno de los tendones de Aquiles que facilitaron el fracaso de Enigma.
Por si ésto solo de por sí no constituyera un sistema robusto, los alemanes lo pulieron aún más, ofreciendo a sus usuarios una logística que se ponía en práctica con determinada frecuencia, consistente en la actualización de documentación relativa a los rotores empleados cada día, el orden en que se colocaban (diferentes entre los distintos ejércitos de tierra, mar o aire), las letras de posición inicial en cada rotor, así como de las posiciones de las clavijas en el panel stecker, y las tablas de codificación de bigramas. Un bigrama es un conjunto de dos letras. En una tabla de 26 x 26 ítems se representaba para cada bigrama original el bigrama transformado correspondiente (era un esquema “hecho a mano” y que también podía variar). De este modo, el protocolo de cifrado establecía que para trabajar con la Enigma de 3 rotores era necesario en primer lugar consultar en la documentación los 3 rotores concretos del día, el orden en que se colocaban, y la letra que tenía que situarse en cada rotor, y además la configuración del clavijero. Después de ésto el operario transmisor elegía 3 letras del alfabeto al azar (la clave), que serían las letras de ventanilla iniciales para usar Enigma en la fase de codificación. Pero antes de ello, las codificaba mediante la Enigma recién configurada y colocaba en un papel cada letra obtenida emparejada con otra elegida al azar debajo de ella. Los tres pares de letras así obtenidos se transformaban mediante la tabla de bigramas y después esos tres bigramas resultantes se colocaban al principio del mensaje. Las 3 letras clave de partida eran las que servían para reconfigurar de nuevo los tres rotores elegidos, y a partir de este punto se empezaba a codificar el mensaje, comenzando la transmisión Morse con los tres bigramas obtenidos a partir de la clave en la operativa antes descrita, pero sin codificar con Enigma, es decir, tal cual se generaron; a lo que seguía ya el mensaje cifrado según lo que fuese “soltando” la máquina mediante los sucesivos cierres de circuitos de corriente. De esta manera, para descifrar se operaba de manera inversa para obtener la clave usada; es decir, se configuraba Enigma con los rotores, posiciones, letras, y clavijas concretos del día; luego se obtenían los 3 bigramas intermedios mediante la tabla de bigramas en sentido inverso. El paso siguiente era coger las tres letras superiores de dichos tres bigramas intermedios y pulsarlas en Enigma, obteniéndose las letras de los rotores empleadas como clave. Se reconfiguraban entonces con ellas los rotores colocándolas como “letras de ventanilla”, y se descodificaba pulsando las letras codificadas y obteniéndose las traspuestas (u originales).
No es muy difícil el darse cuenta de que el número de configuraciones posibles de Enigma era descomunal, del orden de más de diez mil billones de configuraciones. Por ello la máquina Enigma era un sistema muy robusto y dificilísimo de desencriptar. El sistema Enigma viene a ser parecido en cierto modo al 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 posición de los rodillos, y éstos realizaban un avance por cada pulsación de una letra en el teclado, generándose en cada pulsación un nuevo alfabeto de sustitución para la letra siguiente.
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. Se cree que se suicidó comiendo una manzana envenenada con cianuro, aunque la verdad no se conoce con certeza absoluta. En un juicio en el que tuvo que prestar declaración, derivado de un robo perpetrado en su casa, tuvo que confesar que era homosexual, y entonces ésto estaba penado por la jurisdicción británica. Le dieron como opciones ir a la cárcel o someterse a un “tratamiento” de castración química basado en hormonas. Eligió lo segundo, pero la consecuencia fue su pérdida de forma física (era un consumado atleta que incluso estuvo a punto de ser elegido para los primeros Juegos Olímpicos posteriores a la II Guerra Mundial, y ésto le afectó mucho) y las taras psicológicas que posiblemente perturbaron aún más su mente, cosa que para un científico destacado como él lo fue tiene que ser una gran desdicha, al saberse incapaz de pensar con claridad. En otras palabras, le hicieron la vida imposible. Pero sus contribuciones han trascendido por su importancia, para el goce de las generaciones presentes y venideras, y para el bien de la mayor cooperativa mundial, la ciencia; y es a él a quien se le puede atribuir el mérito de ser quizás el primero y mayor de los padres conceptuales de los computadores tal y como hoy los conocemos. Quién sabe a lo que llegaría un espíritu agudo y creativo como el de Turing si no muriese a la edad de 42 años. En cualquier caso, es meridianamente claro que la sociedad y en particular la justicia, no fueron lo que se dice recíprocos con él en relación a las impresionantes contribuciones a la Humanidad, en todo su sentido, con que este genio polifacético del Siglo XX nos obsequió.
RSS: Entradas
