El libro de acceso libre, descargable en PDF, publicado por la Universidad Nacional de General Sarmiento (UNGS), incluye una parte de las contribuciones presentadas, entre el 7 y el 10 de noviembre de 2017, durante las Jornadas Ecos de la Figura y la Obra de Turing en Argentina. Con cierto criterio divulgativo e histórico, la selección de textos se divide en tres secciones. La primera se concentra en la génesis de la “máquina de Turing”, la segunda sobre el rol de Turing en la Segunda Guerra Mundial como matemático a cargo de descifrar mensajes encriptados, y la última sección aborda la relación de Turing con su época y con el mundo contemporáneo. Los escritos compilados por las licenciadas en Matemáticas Eda Cesaratto y Marcela Falsetti, y el sociólogo y escritor Lucas Rozenmacher, pertenecen a especialistas en ciencia y tecnología, computación, matemáticas, criptografía, biología, filosofía e historia.
En buena medida, el punto axial de la publicación lo compone el artículo –el más extenso– del matemático y filósofo Gustavo Piñeiro, en cuanto afronta, si bien no es el único, el Entscheidungsproblem o problema de la decisión, a partir del cual Alan Turing concibe el modelo de la computadora como una ficción matemática. Se trata del artículo de 1936 titulado “On Computable Numbers, with an Application to the Entscheidungsproblem”, en el cual, con el objetivo de superar las limitaciones del teorema de Gödel (esto es, en todo sistema axiomático consistente existen enunciados que no se pueden probar ni refutar, a menos que sea inconsistente), Turing resuelve paradójicamente el problema de decidir –tal el Entscheidungsproblem– si un enunciado es verdadero o no en un sistema axiomático, ya que demuestra que ningún procedimiento algorítmico computable lo soluciona.
De esa manera irónica y muy bella, Turing hace posible determinar, en una suerte de inversión lógica, lo efectivamente computable en los regímenes axiomáticos formales de los sistemas computacionales. La denominada “tesis Church-Turing” (cualquier cuestión computable puede ser resuelta con una máquina de Turing) expresa la equivalencia entre el cálculo lambda de Church y Kleene para definir secuencias algorítmicas calculables –la función computable– y la primera máquina imaginaria de Turing, y ratifica la indecibilidad de los sistemas axiomáticos del teorema de Gödel, a la vez que establece lo positivamente computable por los algoritmos recursivos. En otras palabras, los enunciados que los procesos algorítmicos no pueden resolver en una serie finita de instrucciones es lo que, para Turing, define la calculabilidad o la computabilidad en general. Mejor dicho, la indecibilidad implícita en los sistemas axiomáticos consistentes vuelve factibles las secuencias computables hasta su detención en una meta prefijada y evita que entren en un loop infinito.
Es cierto que Turing, en el artículo “Computing Machinery and Intelligence”, publicado en 1950 –donde propone un célebre test para verificar si las máquinas digitales piensan–, dice, en relación con esa limitación lógico-matemática de las máquinas digitales, que las preguntas no solucionadas por una de ellas podrían ser respondidas por otra. No obstante, la computabilidad no se convierte en decidible (aun en las próximas computadoras cuánticas) debido a un encadenamiento indefinido de máquinas recursivas que corrige los problemas que la anterior no resolvió, porque la condición misma de lo computable es la indecibilidad, la ausencia de un algoritmo que decida la verdad o falsedad de cualquier enunciado matemático.
De modo que si, en efecto, resulta superable la incompletud de cada sistema axiomático en particular; por el contrario, sería imposible suprimirlos en general. Por eso las computadoras quedan a veces detenidas en ciclos muy largos o indefinidos. La programación puede prever si la computadora entrará en un bucle infinito, pero esto no es lo mismo que resolver el inconveniente general, conocido como el problema de detención o halting problem, que radica en saber si un programa se detendrá o no. El artículo de Ana Maffei (doctora en Ciencia y Tecnología) y el matemático y biólogo Tomás Tetzlaff, que se refiere a “la máquina de Turing” –como el de Piñeiro– y los límites de lo computable, reconocen precisamente la importancia del halting problem y demuestran su carácter indecidible. El absurdo de una máquina o programa que pueda responder para toda máquina o programa si habrá detención (o no) es similar a la paradoja del barbero de Bertrand Russell. Esta plantea que en un pueblo hay un barbero que afeita a todos aquellos que no se afeitan a sí mismos, solo que este barbero no puede existir, porque si se afeitara a sí mismo no cumpliría la condición de afeitar a todos los que no se afeitan a sí mismos y tampoco, claro está, si no se afeitara a sí mismo.
En esta paradoja del loop indecidible de los robots algorítmicos, en realidad, culmina la fascinante reconstrucción de Turing, herencias y enigma, de la automatización del cálculo, que creó Turing. De este itinerario constituye un eslabón significativo su experiencia, durante la guerra, como criptógrafo. Sobre el tema de la máquina Enigma, usada –entre otras– por los nazis para encriptar mensajes, en el libro se ocupan Daniel Lvovich (profesor asociado del Área de Historia del Instituto del Desarrollo Humano de la UNGS) y los matemáticos Ariel Waissbein y Nicolás Sirolli, quienes escriben la criptografía mecánica de una época ya lejana.
FRAGMENTOS
La máquina de Turing y los números computables.
El artículo de 1936
En su artículo “Los números computables, con una aplicación al Entscheidungsproblem” [problema de decisión], Turing formalizó la computadora como objeto matemático. Este es el trabajo que le valió el reconocimiento como “padre de la computación”. Cuando uno investiga, lo hace en relación con una pregunta y no porque surge una idea de la nada. Por ese motivo, intenté encontrar cuál era la pregunta que se hizo Turing. Mi interpretación es que la respuesta está en el título del artículo: “una aplicación al Entscheidungsproblem”. En este trabajo define una clase particular de números y los llama computables. Estos se pueden describir como aquellos números cuya expansión decimal, es decir los dígitos que vienen después de la coma, se puede describir mediante métodos finitos. Turing no tuvo miedo al delirio, y describió estos métodos finitos mediante un objeto imaginario al que llamó “máquina”, y finalmente consideró que un número es computable si su parte decimal se puede describir mediante esa máquina.
Métodos finitos, problemas imposibles
Ya hemos definido los números computables como aquellos cuya parte decimal se describe mediante métodos finitos, y los métodos finitos los entendemos como aquellos que pueden ser implementados en una máquina que es un dispositivo mecánico. La máquina ejecuta instrucciones que fueron escritas antes de ser ejecutadas y nos arroja un resultado, una salida, que en general es un número escrito en binario, por ejemplo: 010101. ¡Y es una máquina! Una máquina conformada por piezas simples, como podrían ser algunas varillas y ruedas, dispuestas de tal forma que al funcionar construya tablas de datos. A partir de esta concepción, uno podría dibujar un esquema de un artefacto que transforme energía en tiras de ceros y unos, y definirlo como “máquina finita”. Estos ceros y unos combinados conforman el lenguaje binario. El hecho de elegir ceros y unos es irrelevante, se podrían reemplazar por cualquier otro conjunto de símbolos.
Alan Turing, padre de la computación, por Verónica Becher.
¿Qué es una máquina de Turing?
En 1936, Alan Turing envió para su publicación su artículo titulado “Los números computables, con una aplicación al Entscheidungsproblem”, en el que daba a conocer la descripción de su máquina. De manera simplificada, podemos decir que se compone de una cinta de longitud no acotada, dividida en celdas, en las que se pueden escribir símbolos, por ejemplo ceros y unos, y consta de un cabezal capaz de moverse por la cinta a izquierda y derecha, leyendo y escribiendo sobre las celdas. En cada paso la máquina de Turing se encuentra en cierto estado, lee un símbolo, puede escribir un nuevo símbolo, cambiar de estado y moverse a la celda de la izquierda o a la celda de la derecha. Por ejemplo la instrucción (A, 1, 0, I, B) establece que si la máquina está en el estado A y lee un 1, escribe un 0, se mueve a la izquierda y pasa al estado B. Con combinaciones de instrucciones de este tipo se pueden hacer operaciones aritméticas y lógicas elementales y también implementar algoritmos complejos. Además, una máquina de Turing se puede construir físicamente, excepto por la cinta infinita, que correspondería a una disponibilidad de memoria no acotada para una computadora moderna, algo no demasiado irreal hoy en día con todas las posibilidades de almacenamiento que existen. El problema que tiene programar con una máquina de Turing es que el número de instrucciones y la dificultad para combinarlas, aun para una tarea bastante sencilla, es mucho mayor que con un lenguaje de computación moderno.
Como pequeño ejemplo, veamos una máquina en la que el cabezal recorre la cinta hacia la derecha cambiando todos los ceros por unos hasta que encuentra el primer 1 y allí se detiene (y si no encuentra un 1 no se detiene). Las dos instrucciones que mostramos a continuación definen completamente esta máquina, que comienza en estado A:
Instrucción (A, 0, 1, D, A): en el estado A y leyendo un 0, se escribe sobre él un 1, se mueve el cabezal a la derecha y se sigue en estado A.
Instrucción (A, 1, 1, D, H): en el estado A y leyendo un 1, se mantiene el 1, se mueve el cabezal a la derecha y se pasa al estado H, que significa detención.
Con su formalización Turing hizo preciso el concepto de número computable, aquel para el cual existe una máquina de Turing que devuelve el n -ésimo dígito de su desarrollo decimal en un número finito de pasos. Pero su invento tiene una aplicación mucho más general gracias a su ingeniosa exploración de los límites que aparecen cuando se estudia la posibilidad de que un algoritmo ejecute otro algoritmo como parte de sus instrucciones. Esto último es una parte fundamental de la práctica de la programación. Se presenta por ejemplo cuando una aplicación que muestra una lista de nombres en la pantalla llama a su vez a un subprograma para que los ordene alfabéticamente, o cuando un ciclo va recorriendo los números menores que un número n para ver si alguno es divisor de n. De hecho un ciclo es un algoritmo que se llama a sí mismo en la última instrucción, usualmente hasta que se cumple alguna condición. Veremos que aun sin los variados ejemplos que provee la programación actual sobre la posibilidad de que un procedimiento llame a otro o incluso a sí mismo, Turing encontró límites siempre vigentes para el poder de las computadoras.
En las máquinas de Turing está el poder y los límites de la computación, por Ana Maffei y Tomás Tetzlaff.
Primera versión del ‘Entscheidungsproblem’
Dada una ecuación diofántica cualquiera, el décimo problema de Hilbert pide “idear un procedimiento de acuerdo con el cual pueda determinarse, en un número finito de operaciones, si la ecuación tiene soluciones enteras”. ¿Qué entiende Hilbert por un “procedimiento”? Hilbert llama “procedimiento” al concepto que hoy en día se conoce como un “procedimiento efectivo” o, más comúnmente, como un “algoritmo”.
¿Qué es, entonces, un algoritmo? Intuitivamente, es una receta que puede seguirse mecánicamente paso a paso sin necesidad de pensar. Los programas de computadora, o las aplicaciones de los celulares, son ejemplos bien conocidos de algoritmos. Por este motivo, podemos traducir el décimo problema de Hilbert al lenguaje del siglo XXI de la siguiente manera: ¿es posible programar una computadora de tal modo que, dada una ecuación diofántica (una ecuación en la cual las incógnitas aparecen sumadas, restadas, multiplicadas entre sí, o elevadas a potencias enteras positivas, y en la que solo figuran coeficientes enteros) cualquiera, determine en una cantidad finita de pasos (o una cantidad finita de tiempo) si la ecuación tiene, o no tiene, solución?
Este problema es, históricamente, la primera versión del famoso Entscheidungsproblem, o problema de la decisión, de Hilbert. Como se dijo en el capítulo 2, en su forma más general, el Entscheidungsproblem propone la siguiente cuestión. Tomemos una teoría matemática cualquiera y consideremos, dentro de esa teoría, una familia amplia de preguntas que pueden ser respondidas por “sí” o por “no”. El Entscheidungsproblem plantea si existe un algoritmo que permita responder, en una cantidad finita de pasos, cualquiera de esas preguntas. En el caso particular del décimo problema, tenemos una pregunta para cada ecuación diofántica, que es, obviamente, si la ecuación tiene solución.
En una forma más rigurosa, el Entscheidungsproblem plantea, dado un sistema de axiomas y un enunciado matemático P, si existe un algoritmo que determine, en una cantidad finita de pasos, si P es demostrable a partir de esos axiomas. Esta formulación equivale a la que comentamos en el párrafo anterior si entendemos que los axiomas son la base de alguna teoría matemática y el enunciado P se ve como una conjetura de la que quiere saberse si es verdadera o falsa.
El sueño de Hilbert, las máquinas de Turing y los teoremas de Gödel, por Gustavo Piñeiro.
La contribución de Turing a la guerra
En el proyecto Manhattan participaron, además de algunas personas célebres, como Einstein y Oppenheimer, unas 130 mil personas, lo que supone la existencia de todo un Estado haciendo inversiones de capital y humanas orientando el conjunto de la economía de una manera decisiva para alcanzar este objetivo.
En el caso de la organización en que se inserta Turing, fueron 10 mil las personas involucradas, lo que implica un esfuerzo económico y organizativo de vasto alcance. Alan Turing estaba trabajando desde antes de su doctorado en temas similares, pero ya para septiembre de 1939 se había incorporado al servicio de criptografía de la inteligencia británica. Tenía 26 años en ese momento.
No voy a desarrollar los modos en que logra romper los códigos de Enigma, el sistema que los alemanes usaban para encriptar sus mensajes, pues de ello se ocupa el capítulo 5. Pero puedo brindar algunos datos para medir la efectividad del trabajo de Turing para desencriptar los códigos alemanes. En el año 1940, son hundidos 520 buques aliados que iban hacia Inglaterra, en 1941 pasan a ser 456, en 1942 son 1.155 las embarcaciones que se hundieron, pero cuando se descifra al año siguiente el código alemán, la cifra se redujo nuevamente a 452 hundimientos. Tanto en el desarrollo de la guerra en el Mediterráneo y en el norte de África como en el frente ruso, la información aportada por el Servicio Británico de Descifrado fue fundamental. Se sabe que unos días antes del desembarco en Normandía, los aliados sabían que los alemanes creían que el desembarco iba a ser en el paso de Calais y no en Normandía, a través del descifrado de los textos encriptados por las máquinas Enigma. Por eso se estima que la contribución de Turing a la guerra fue fundamental y que logró evitar millones de muertes y reorientar decisivamente el curso de la guerra.
El destino personal de Alan Turing no fue acompañado por la gloria que sí obtuvieron los generales victoriosos. Todo su trabajo permaneció en secreto hasta la década de 1970, y en 1952 fue procesado por homosexualidad, condición que era penada por la ley en Inglaterra hasta 1967. Turing murió en la cárcel, dos años después de su condena, en circunstancias nunca del todo aclaradas. Recién en 2013 se exoneró a Turing y se anularon los cargos en su contra.
El contexto de la obra de Alan Turing: la Segunda Guerra Mundial, por Daniel Lvovich.
El funcionamiento de Enigma
El aspecto exterior de la Enigma es como el de una máquina de escribir antigua un poco aparatosa. Desde afuera, se puede apreciar que, además del teclado en el que se presionan las letras para escribir el texto, tiene un tablero con las veintiséis letras del alfabeto (los alemanes no tienen “ñ”), cada letra con una lamparita pequeña, un clavijero y unas ruedas dentadas que son los rotores (tres o más, depende de la versión). Cada rotor tiene al lado un pequeño indicador que muestra su posición, como las perillas de la cocina, y tiene 26 posiciones posibles, indicadas con una letra. Como en los sistemas actuales, para comenzar hay que introducir una clave en la máquina. Supongamos que tenemos una máquina de tres rotores. La clave tendrá entonces tres letras. El operador, la persona que usa la máquina, posiciona cada rotor según la letra de su clave; toma el texto “llano” (un texto inteligible por una persona que conoce el idioma en el que está escrito) que tiene anotado en un papel y teclea en el teclado la primera letra; en ese momento, una corriente eléctrica pasa por el cableado interno e ilumina la letra correspondiente del texto encriptado en el tablero. El operador anota la letra que salió y continúa con la segunda letra de su texto. Toda la operatoria se hacía manualmente. Una vez encriptado el mensaje, se lo pasaba por telégrafo al destinatario del mensaje. Ambos, destinatario y emisor, conocían la clave secreta (cómo se habían puesto de acuerdo es otro tema). El destinatario acomodaba los rotores según la clave, tecleaba el texto encriptado y obtenía el texto llano.
Ahora tratemos de entender el funcionamiento interno. Esta explicación se basa en el excelente libro de Simon Singh Los códigos secretos. La versión más simple de la máquina tiene tres rotores. Cada rotor es un cilindro chato con dos tapas de metal y una goma interna llena de cables, como una especie de alfajor. No se puede abrir. Cada rotor tiene tantos cables como letras del alfabeto y cada cable va desde una tapa a la otra uniendo una entrada y una salida.
La criptografía mecánica de la Segunda Guerra, por Ariel Waissbein.
