El enigma de Turing (parte 2)

Segunda parte de la serie sobre Alan Turing en el centenario de su nacimiento. La primera parte está acá.

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 NUMBERS

Su 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.

¿Y qué es un número computable? Bueno, un número computable es un número cuyos decimales pueden ser escritos por una máquina. Era algo muy raro de decir en 1936. “Computadora”, en esa época, no significaba una máquina, como significa ahora. Significaba una persona, en general una chica. Una persona que calcula. Lo que propone Turing es automatizar todo el proceso para que en lugar de una persona lo haga una máquina. Habían existido máquinas de calcular en siglos anteriores, y en ese mismo momento se estaban diseñando máquinas de calcular, de sumar, de resolver ecuaciones diferenciales. Pero lo cierto es que en 1936 no existía ninguna máquina capaz de hacer lo que Turing pedía de manera tan general. Las computadoras (en el sentido moderno) no existían. Turing sacó el concepto de su galera matemática. Sólo años más tarde la tecnología electrónica permitiría convertir estas ideas en verdadera ingeniería.

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.

La máquina es increíblemente sencilla. En la figura muestro un ejemplo. Tiene un "scanner" que se desplaza sobre la cinta, leyendo los números uno por uno. La máquina tiene un conjunto de estados posibles. El scanner es el trapecio negro, que además muestra el estado de la máquina en cada paso de tiempo. La nubecita muestra el número leído por el scanner. La "tarea repetitiva y metódica" está especificada mediante una tabla que, de acuerdo al estado y al número leído, dice qué tiene que hacer. Y lo que puede hacer es muy limitado: puede borrar o escribir un número, puede cambiar de estado, y puede moverse a la izquierda o a la derecha. La tabla de este ejemplo define una máquina que suma dos números. En la cinta están inicialmente escritos los números 3 y 4 (en representación "unaria"), y la máquina los suma, así como muestra la animación. Fijensé, no hay trampa. La máquina suma. En terminología moderna, el “método” que lleva a cabo la máquina es un algoritmo. La tabla que define las operaciones que hace la máquina con los símbolos impresos, es el software. Turing inventó el software.

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!

Con un método diagonal inventado por Georg Cantor en el siglo XIX, y que también es central en el razonamiento de Gödel, es fácil construir un número no computable. La idea está ilustrada en la figura. Supongamos que tenemos todas las máquinas ya numeradas y prolijamente ordenadas. La primera máquina, por ejemplo, computa el número 1. La segunda, digamos, computa pi. La tercera un pi aproximado, etc, etc. Ahora escribimos un número de la siguiente manera, que nos asegura que el número no está en la tabla (es el número de colores de la fila amarilla en la figura): miramos el primer dígito del número computado por T₁, y lo cambiamos (por ejemplo, sumando 1). Después revisamos el segundo número, encontramos su segundo dígito, y hacemos lo mismo. Así vamos recorriendo la diagonal de la tabla, y escribiendo un número cuyo i-ésimo dígito es distinto del i-ésimo dígito del i-ésimo número. Este número no está en la lista, así que no es un número computable. ¿Por qué? ¿No podría haber una máquina T_j, con j por ahí abajo, que compute este número? No, porque el j-ésimo dígito del número computado por T_j es distinto del j-ésimo dígito del número colorido. ¡Así lo construímos! Y como en la tabla están todas las máquinas que computan números, no hay ninguna máquina que pueda computar el número de colores. Chan.

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 T₁, 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...