Dónde estábamos: Alan tomó el curso de Lógica Matemática de Max Newman en King's College. Terminaba con los teoremas de Gödel, que daban por tierra con el ambicioso Programa de Hilbert. Turing se interesó en un resquicio que Gödel no había resuelto, el Entscheidungsproblem, el problema de la decidibilidad: ¿Existe un método para decidir si una dada afirmación matemática es demostrable? Turing resolvió este problema, trabajando en completa soledad a los 23 años de edad, y de paso en el camino inventó la ciencia de la computación.
COMPUTABLE NUMBERSSu contribución está en este trabajo, publicado en 1936 en los Proceedings de la London Mathematical Society. Tiene un título intimidante, con una palabra inventada, “computable”, y la famosa palabra de Hilbert tan difícil de pronunciar sin que alguien diga ¡salud!. Es notable que Turing ponga el énfasis del título en los números computables y no en la demostración del problema de Hilbert. A pesar de la relevancia académica de resolver un problema de Hilbert, parece que Turing se diera cuenta de que lo que había inventado estaba bueno, y que el problema de la decisión resultaba apenas una aplicación. Pero en realidad nadie (ni siquiera Turing) se dio remotamente cuenta de su profundo significado hasta mucho tiempo después. Todas las computadoras modernas, desde las laptops a los videojuegos, desde los teléfonos hasta los robots que aterrizan en Marte, son exactamente lo que Turing mostró en este paper.
En la segunda página del artículo, promediando el larguísimo resumen, nos encontramos con la conclusión de Turing (segundo recuadro en la imagen): el Entscheidungsproblem no tiene solución. En las siguientes 28 páginas Turing no vuelve a hablar del Entscheidungsproblem.
Alan le mostró el manuscrito a su profesor de Lógica. Newman había recibido justo en esos días un preprint de Alonzo Church, un matemático norteamericano de la prestigiosa escuela de Lógica de Princeton. Al mismo tiempo que Turing y de manera independiente Church había llegado a la misma conclusión sobre el problema de la decidibilidad. Así que parte de la originalidad del trabajo de Turing se desvaneció. El approach de Church era de todos modos muy diferente, eso quedó claro desde el principio. Y además estaba el valor teórico de lo que llegaría a ser el fundamento de la ciencia de la computación. Así que Newman apoyó la publicación del trabajo. Pero Alan tuvo que agregar a último momento ese párrafo que vemos asomar en la imagen, al final del largo resumen. Y agregó también un apéndice demostrando la equivalencia entre su “computabilidad” y la “calculabilidad efectiva” de Church.
Si uno sobrevive al título, es posible que la tipografía gótica de la notación termine de intimidarlo. Afortunadamente existe un libro, The Annotated Turing, de Charles Petzold, donde se explica todo párrafo por párrafo.
MÁQUINAS DE TURING
Como decíamos, la cuestión de la decidibilidad era la inspiración del trabajo, pero la mayor parte del mismo se trata de lo que Turing llama “números computables”, cuyo estudio ocupa el primer 60% del artículo, y que se pueden entender sin saber nada de Lógica ni del Programa de Hilbert.
Turing empieza a explicar lo que quiere decir por “calculable por una máquina”. La justificación viene de la asociación entre lo humano y la máquina, que se convertiría en un tema central a lo largo de toda su obra. Se plantea la cuestión de qué podría lograr una persona llevando a cabo una tarea metódica, repetitiva y mecánica. Y esto lo lleva a formular su análisis en términos de una “máquina” teórica, capaz de realizar operaciones elementales, predefinidas, sobre una secuencia de símbolos impresos en una cinta de papel. Argumenta que cualquier cosa que a uno se le pueda ocurrir que significa “metódico”, esta máquina lo podría hacer tan bien como una persona.
Turing muestra cómo estas máquinas, así de sencillas, no sólo pueden escribir sus "números computables", sino que también pueden llevar adelante cualquier cálculo matemático imaginable, tan sólo moviendo unos y ceros de atrás para adelante y de adelante para atrás. Más aún, cualquier tipo de información podía codificarse numéricamente y procesarse de la manera que uno quisiese. Como ven, son todos conceptos súper familiares para nosotros. No así en 1936. Fue el momento en que nació la Era Digital.
Un número computable, entonces, es un número que una de estas máquinas escribe en una cinta de papel. Claramente, los números enteros son computables. También los números racionales, las fracciones. Aun las que tienen un desarrollo decimal con infinitas cifras, como 1/3. ¿Y los números más raros? Pi, por ejemplo, es computable. Obvio, ya que sabemos cómo calcularlo con cuantos decimales queramos, con lápiz y papel. Lo mismo con la raíz cuadrada de 2, etc. Esto de los números computables es bastante loco. Parecen no tener una relación obvia con los números irracionales, o con los números trascendentes, o cualquiera de las otras categorías que conocemos. ¿Entonces? ¿Todos los números reales serán computables?
No. Turing demuestra que estas máquinas, que tienen un número finito de estados posibles, son enumerables, es decir son tantas como los números naturales. Y hay muchos más números reales que números naturales. Muchos, muchos más. Así que la mayor parte de los números son no computables. No importa cuánto nos esforcemos, nunca aparecerán como resultado de nuestros cálculos. ¿No es loquísimo? Cabe preguntarse qué tan reales son los números reales que no son computables. Así que hoy en día hay toda una rama del análisis de los números computables en lugar de los reales.
Bueno. Ya que las máquinas son numerables, Turing las numera. Es decir, muestra cómo se pueden codificar las tablas (que definen a las máquinas) de manera numérica. Es un lío, pero se puede hacer metódicamente. Uno termina con una máquina descripta, en lugar de por símbolos que representan las operaciones, por una “definición estándard” que es un número entero. Es claramente un approach inspirado en el Teorema de Gödel y su codificación numérica de las expresiones matemáticas. De yapa, tenemos una manera de generar máquinas de Turing: los números enteros. Muchas de ellas no funcionarán, muchas calcularán trivialidades, otras calcularán las mismas cosas de maneras diferentes, algunas más rápido, algunas más lento, algunas con pequeñas diferencias... Algunas ni siquiera se detendrán. ¡Es como la Biblioteca de Babel de Borges!
LA MÁQUINA UNIVERSAL
Pero ¿no hay aquí una contradicción? El método de Cantor es tan fácil de explicar que parece completamente mecanizable, ¿cómo puede ser que ese número sea no computable? ¿No debería haber una “máquina de Cantor” capaz de calcularlo? Esta máquina debería producir la tabla de la máquina T1, ejecutarla hasta el primer dígito, sumar 1 y escribir, después producir la segunda máquina, ejecutarla hasta el segundo dígito, sumar 1 y escribir, y así siguiendo. Es decir, debe ser una máquina capaz de emular lo que hacen las otras máquinas. Una máquina universal.
En algún sentido, la Máquina Universal de Turing es la única que necesitamos: no se necesita una máquina para cada tarea computable. La máquina universal ha llegado para acabar con todas las máquinas. La máquina universal es, decimos hoy, programable.
La máquina universal es tan importante para el argumento de Turing que éste la construye con todo detalle, dando explícitamente su tabla de estados y operaciones, a un nivel que es muy difícil de asimilar con facilidad. Si uno ha de creerle al Annotated Turing, además, la descripción no está libre de bugs. Pero, dejando de lado esto, Turing acababa de hacer algo extraordinario: había demostrado la generalidad de la computación, había mostrando cómo una máquina programable puede llevar a cabo la operación de cualquier máquina de computar. Es sin duda uno de los grandes logros intelectuales del siglo XX.
Ciertamente, Turing no “inventó” la computadora. Pero hasta ese momento la suposición habitual en la gente que trabajaba en el tema era que cada computadora debería ser diseñada para un propósito específico. Aún en la década del 50, más de 15 años después de Computable Numbers, los ingenieros que diseñaban las primeras computadoras digitales no habían acabado de visualizar a la computadora como una herramienta lógica, más que de cálculo. Así que no es de sorprender que el rol de Turing en la historia de la computación se cuente de manera desigual en distintos libros. Una cosa es contar la historia de la computadora desde un punto de vista de la ingeniería o del mercado. Y otro es el punto de vista que considera a las computadoras como materializaciones de conceptos matemáticos. En este último caso, el papel de Turing es destacadísimo.
¿Y el Entscheidungsproblem?
El método diagonal es la clave. La cosa se vuelve sumamente técnica y, depués de todo, no es más que "una aplicación" de las Máquinas. Turing muestra primero que puede construir una máquina que codifica todo el cálculo funcional de Hilbert. Muestra que el Entscheidungsproblem es equivalente a demostrar si la máquina que calcula el número construido con el método diagonal se detiene, y demuestra que este problema no tiene solución. Piece of cake.
PRINCETON
Como no podía ser de otra manera, Turing se fue a Princeton, donde se quedó dos años. Church dirigió su tesis, que completó en 1938. Princeton se había convertido en una meca para la física y la matemática, particularmente con la creación del Instituto de Estudios Avanzados. Gödel lo visitaba todos los años y John von Neumann, Courant, Hardy, Weyl, Einstein y tantos otros se habían establecido allí, muchos de ellos escapando del régimen nazi.
Sus ideas alcanzaron cierta notoriedad, atrayendo incluso la atención de von Neumann, a quien le había encantado Computable Numbers (otro día tal vez hablemos de él). Pero no saltó a la fama ni mucho menos. Su trabajo en Princeton, incluyendo la demostración de que sus conclusiones sobre la decidibilidad coincidían con las de Church, fue el material de su tesis. Esta línea de trabajo, tal vez la más profunda de su carrera, no prosiguió más allá de su doctorado.
Durante su segundo año en Princeton, mientras terminaba la tesis, la situación política en Europa se complicaba cada vez más. Estaba claro que Inglaterra y Alemania pronto entrarían en guerra. A pesar de que von Neumann le ofreció un tentador puesto en el Instituto de Estudios Avanzados, Turing se volvió a Inglaterra, donde no tenía trabajo. Apenas consiguió una beca de King’s College.
Pero rápidamente consiguió un trabajo mejor. Un trabajo secreto, que salvó miles de vidas, permitió la supervivencia de Inglaterra, y ayudó a los Aliados a ganar la guerra.
Continúa en la Parte 3 de El enigma de Turing...
