El libro The Annotated Turing escrito por Charles Petzold y publicado en el año 2008, hace una extensa revisión del artículo original donde Alan Turing (1912-1954) presenta una máquina imaginaria de computación que ahora conocemos como Máquina de Turing (aunque el autor no la llamó así) y, además, muchos años antes de que alguien hubiese demostrado lo que un computador puede hacer, él probó teóricamente lo que un computador NO puede hacer.
Sin embargo, aunque el artículo “On Computable Numbers, with an Application to the Entscheidungsproblem” (“Sobre los números computables, con una aplicación al problema de decisión”) publicado en 1936 en la revista Proceedings of the London Mathematical Society, es el documento seminal de la teoría de la computación, en la práctica es poco leído -incluso por los estudioso de la computabilidad-. A continuación presento una traducción [un tanto libre] de las primeras páginas del capítulo 8 “Everything is a Number“, como una invitación a leer el libro mencionado.
Todo es un número
En la era digital crecimos acostumbrados a representar todas las formas de información como números. Textos, dibujos, fotografías, sonidos, música, películas – todo va al molino de la digitalización y luego se puede almacenar en nuestros computadores y otros dispositivos como complejos ordenamientos de unos y ceros.
Sin embargo, en la década de 1930, los número solo eran números, y si alguien intentaba convertir texto a números , era con el propósito de engañar e intrigar.
En el otoño de 1937, Alan Turing iniciaba su segundo año en [la universidad de] Princeton en medio del temor agudizado que Inglaterra y Alemania pronto estuvieran en guerra. Él estaba trabajando en su tesis doctoral pero había desarrollado interés en estudiar criptología – la ciencia y matemática para crear códigos secretos o cifradores (criptografía) y descifrar los códigos inventados por otros (criptoanálisis). Turing consideraba que los mensajes durante la guerra podrían cifrarse mejor si las palabras se convertían a dígitos binarios y luego se multiplicaban por números grandes. Descifrar los mensajes sin el conocimiento de dicho número grande sería un problema de factorización muy difícil. Esta idea de Turing era algo profética, pues es la forma en que los computadores actualmente hacen uso de la criptografía.
A diferencia de la mayoría de matemáticos, a Turing le agradaba ensuciarse las manos construyendo cosas. Para implementar una máquina de codificación automática él comenzó a construir un multiplicador binario utilizando relevos (relays) electromagnéticos, que eran los principales bloques de construcción de computadores antes de que los tubos de vacío demostraran que eran lo suficientemente confiables. Turing incluso construyó sus propios relevos (relays) en un taller y elaboró las bobinas él mismo.
En aquel momento el ejercito y la naval de Alemania estaban utilizando un dispositivo de cifrado muy diferente. La máquina Enigma fue construida por un ingeniero eléctrico alemán llamado Arthur Scherbius (1878-1929). Después que Scherbius había intentado infructuosamente en 1918 de persuadir a la naval alemana para que utilizara la máquina, la había puesto a la venta para uso comercial en 1923. La naval llegó a interesarse en la máquina poco después de esto, eventualmente seguida por las otras fuerzas militares alemanas.
Enigma tenía un teclado rudimentario de 26 teclas dispuestas como una máquina de escribir pero sin números, sin signos de puntuación, ni tecla para mayúsculas. Arriba del teclado había 26 bombillas luminiscentes colocadas con el mismo patrón. Los mensajes eran cifrados digitándolos en el teclado. A medida que cada letra era oprimida, una letra diferente a la presionada se iluminaba. Las letras iluminadas eran copiadas a mano para luego ser enviadas al destinatario. (El mensaje cifrado podía ser entregado en la mano o enviado por correo postal. Tiempo después los mensajes cifrados fueron enviados mediante señales de radio utilizando código Morse.) La persona que recibía el mensaje tenía su propia máquina Enigma, y podía mecanografíar el mensaje cifrado en el teclado. Las luces que se encendían iban mostrando el mensaje original.
Cada tecla estaba conectada eléctricamente a las bombillas a través de una seria de rotores. Cada rotor era un pequeño disco con 26 contactos en cada lado representando las letras del alfabeto. Dentro del rotor, estos contactos estaban conectados simétricamente: si el contacto “A” de un lado del rotor conectaba el contacto “T” del otro lado, entonces el contacto “T” del primer lado conectaba el contacto “A” del segundo lado. Esta simetría era la que permitía que la máquina pudiera ser utilizada tanto para cifrar como para descifrar.
La Enigma estándar tenía tres rotores conectados, cada uno de los cuales estaba interconectado de forma diferente, y cada uno podía ser colocado en una de 26 posiciones diferentes. Los tres rotores utilizados en las máquinas para cifrar y descifrar tenía que ser idénticos. Las tres posiciones (letras) iniciales de los tres rotores podía cambiarse cada día de acuerdo con una lista conocida sólo por los operadores de las máquinas Enigma.
Hasta aquí, lo descrito de la Enigma la muestra como una máquina apenas capaz de trabajar con un código para la sustitución de letras que se puede romper fácilmente incluso por un criptoanalista aficionado. Es aún más simple que la mayoría de códigos de sustitución ya que es simétrica: Si la “D” es codificada como una “S” entonces la “S” será codificada como una “D”.
Aquí está la sorpresa: a medida que el usuario de la Enigma presiona las teclas, los rotores se mueven. Con cada presión de tecla, el primer rotor se mueve adelante una posición. Por ejemplo, si se escribe una cadena de 26 letras “A”, cada “A” sucesiva será codificada diferente a medida que el rotor pasa por las 26 posiciones que tiene. Cuando el primer rotor ha terminado una vuelta completa, la máquina moverá el segundo rotor una posición adelante. Ahora, si se escribe otra cadena de 26 letras “A”, cada “A” será codificada de manera diferente a la anterior secuencia de de “A”s. Cuando el segundo rotor haya dado una revolución completa (26 cambios de posición), la máquina moverá el tercer rotor una posición adelante. Un cuarto rotor estacionario llevará la señal eléctrica de vuelta a través de los rotores en orden inverso. Solo después de 17.576 presiones de tecla (es decir, 26 a la tercera potencia) se repetirá el patrón de cifrado.
Pero un momento, aún es peor: los rotores se pueden reemplazar. La máquina básica era vendida con cinco rotores diferentes, que podían ser utilizados en cualquiera de las tres ranuras para los rotores. Otra mejora incluía un tablero que se podía enchufar y que agregaba otra capa de mezclado de las letras. 
En 1932, tres matemáticos polacos comenzaron a desarrollar métodos para decodificar los mensajes creados con la máquina Enigma. Ellos determinaron que necesitaban construir dispositivos que simularan a Enigma de una manera automática. Las primeras “bombs” [bombas] (como ellos las llamaron) estuvieron operativas en 1938 y buscaban a través de las posibles posiciones de los rotores. Uno de estos matemáticos era Marian Rejewski (1905-1980), quien había estado un año en Göttingen después de graduarse. El escribió que las máquinas habían sido llamadas “bombs” “por falta de un mejor nombre” pero que era posible que el nombre evocara el sonido de tic-tac que hacían o por cierta copa de helado que le gustaba a los matemáticos.
Tradicionalmente, el gobierno británico había empleado investigadores académicos tradicionales para romper códigos bajo el supuesto razonable que eran las personas mejor entrenadas para decodificar lenguajes difíciles. A medida que la guerra se aproximaba, se hizo evidente que para realizar el análisis de dispositivos de codificación sofisticados como Enigma, la GC & CS (Government Code and Cypher School ) requeriría también de matemáticos.
Cuando Alan Turing regresó de Princeton a Inglaterra en el verano de 1938, él fue invitado a tomar un curso en los cuarteles de la GC & CS. Es posible que el gobierno estuviese en contacto con él desde comienzos de 1936. En 1939, la GC & CS compró un gran terreno de una mansión victoriana llamada Bletchley Park que estaba a 50 millas al noroeste de Londres. En cierto sentido, Bletchley Park fue el punto focal intelectual de Inglaterra – donde la vía ferrea entre Oxford y Cambridge conectaba con la vía ferrea al sur de Londres.
El primero de septiembre de 1939 Alemania invadió Polonia. Dos días después, Gran Bretaña declaró la guerra a Alemania y el cuatro de septiembre Alan Turing se reportó en cumplimiento de su deber en Bletchley Park. Eventualmente cerca de diez mil personas trabajaban allí interceptando y codificando comunicaciones secretas. Para alojarlos a todos, se construyeron cabañas alrededor de los terrenos. Turing estaba a cargo de la cabaña 8, dedicado al descifrado de códigos utilizados por la naval alemana. Los alemanes utilizaban estos códigos para comunicarse con los submarinos, que eran una amenaza particular para los convoys en el Atlántico entre los Estados Unidos y Gran Bretaña.
A comienzos de 1939, los británicos se habían reunido con los matemáticos polacos `para aprender acerca de la máquinas Enigma y las “bombs”. Recién Turing inició en Bletchley Park, él comenzó a rediseñar y mejorar los dispositivos, conocidos ahora con la grafía francesa de bombe. La primera Turing Bombe (como son llamadas a veces) estuvo operativa en 1940. Pesaba una tonelada y podía simular 30 máquinas Enigma trabajando en paralelo.
Antes de atacar los mensajes con la Turing Bombe, fue necesario reducir las posibilidades. Los criptoanalistas buscaban “cribs” [apunte oculto para copiar en los exámenes], que eran palabras o frases comunes que aparecían a menudo en los mensajes codificados. Estos podían establecer la posición inicial del primer rotor. Más valiosos eran los mismos mensajes que eran trasmitidos utilizando dos codificaciones diferentes: estos eran conocidos como “kisses“. Otra técnica utilizaba papel blanco de alto gramaje con anchos diversos impreso con múltiples filas del alfabeto, de forma similar a las tarjetas perforadas que se usaron después con los computadores. El analista hacia agujeros en el papel donde estaba una letra del mensaje cifrado. Diferentes mensajes del mismo día (que podían estar basados en la misma configuración de Enigma) podían entonces ser comparados superponiendo las hojas con perforaciones. Debido a que el papel utilizado venía de una ciudad cercana llamada Banbury, el procedimiento fue llamado “banburismus”.
Esta diversidad de técnicas fueron refinadas hasta el punto que, para mediados de 1941, el éxito logrado en la decodificación de las comunicaciones de Enigma había reducido mucho las pérdidas navales. Muchas de las personas que trabajaron en Bletchley Park merecen el crédito por lograr este éxito, sin embargo el trabajo de Alan Turing jugó un papel significativo.
Para estar en una inusual reunión de matemáticos y académicos clásicos en Bletchley Park, Turing logró tener reputación de excéntrico.
“En la primera semana de Junio de cada año [Turing] podía padecer un ataque de fiebre del heno, y podía ir en bicicleta a la oficina usando una máscara anti-gas para protegerse del polen. Su bicicleta tenía una falla: la cadena podía caerse en intervalos regulares. En lugar de repararla, él contaba el número de veces que los pedales daban una vuelta completa y descendía de la bicicleta a tiempo para ajustar la cadena manualmente. ” [I. J. Good]
En la primavera de 1941, Alan Turing le propuso matrimonio a Joan Clarke, una de las raras mujeres en Blentchle Park que no estaba relegada a hacer trabajo de oficina. Joan Clarke estaba estudiado matemáticas en Cambridge cuando fue reclutada para romper códigos. Unos pocos días después de la propuesta Turing le confesó que él tenía “tendencias homosexuales”, sin embargo el compromiso continuó por varios meses más antes que él sintiera que debía cancelarlo.
En noviembre de 1942, Turing fue enviado en una misión a Washintong, D.C., para ayudar a coordinar actividades para romper códigos entre Inglaterra y los estados Unidos. Durante esta asignación, el permaneció los dos primeros meses de 1943 en los laboratorios Bell, cuando estaban ubicados en West Street en Nueva York. Allí conoció a Harry Nyquist (1889-1976) quien lideraba la teoría de muestreo digital, y a Claude Elwood Shannon (1916-2001), cuyo artículo “A Mathematical Theory of Communication” (1948) fundaría el campo de la teoría de la información y presentó la palabra “bit” al mundo.
El principal objeto de interés de Turing en los laboratorios Bell fue un dispositivo de mezcla de voz que pretendía dar seguridad a las comunicaciones telefónicas sobre el Atlántico. Las ondas sonoras eran separadas en varios rangos de frecuencias, digitalizadas y luego cifradas con suma modular, que es una suma cuyos resultados están dentro de un conjunto finito de valores (como cuando sumamos segundos y minutos y el conjunto de valores posibles está entre 1 y 60). Del lado del receptor, los números eran descifrados y re-ensamblados como un mensaje de voz.
En la investigación de Nyquist, el trabajo de Shannon y el dispositivo de cifrado, podemos observar el origen de las ideas que después dieron como resultado las tecnologías utilizadas para digitalizar imágenes en archivos con formato JPEG y sonidos en archivos con formato MPEG, pero estas innovaciones en particular requirieron décadas para su realización práctica.
Por otra parte, los primeros computadores digitales solo entregaban números. Inclusive la máquina de diferencias de Babbage estaba concebida solo para imprimir tablas de logaritmos libres de errores. En este contexto, no causa sorpresa que las máquinas de Turing también generen números en lugar de, por ejemplo, implementar funciones generalizadas.
Turing enfocó su artículo [“On Computable Numbers, with an Application to the Entscheidungsproblem“] en una dirección inusual al utilizar números para codificar otras formas de información. La siguiente sección del artículo del artículo de Turing [Sección 5. Enumeration of computable sequences] demuestra cómo los números pueden representar no solo fotografías o canciones, si no que pueden representar las máquinas mismas.
Sí, todo es un número. Incluso las máquinas de Turing son números.
Tomado de “The Annotated Turing” de Charles Petzold. Wiley Publishing, Inc. 2008.