La máquina de Turing

La máquina de Turing (en inglés, Turing machine) es un aparato imaginario que calcula con los medios más pobres que se pueden concebir: una cinta dividida en casillas, un cabezal que lee y escribe un símbolo en la casilla que tiene delante y se mueve una posición a la izquierda o a la derecha, y una tabla finita de reglas que dice qué hacer según el símbolo leído y el estado (state) en que se encuentra la máquina. Nada más. No tiene memoria aparte de la cinta, no sabe sumar, no ve más que una casilla cada vez. Y sin embargo todo lo que hace cualquier ordenador actual, desde una hoja de cálculo hasta un modelo de lenguaje, lo puede hacer también una máquina de Turing, más despacio y con una cinta más larga. Esa es la tesis que la hace importante, y también la razón de que lo más interesante de ella sea lo que no puede hacer.

Alan Turing la describió en un artículo que envió a la London Mathematical Society en mayo de 1936, cuando tenía veintitrés años y era fellow del King’s College de Cambridge. No pretendía diseñar un ordenador, que todavía no existía, sino contestar una pregunta de lógica. David Hilbert y Wilhelm Ackermann habían planteado en 1928 el Entscheidungsproblem, el problema de la decisión: ¿existe un procedimiento mecánico que, dada cualquier afirmación de la lógica matemática, decida en un número finito de pasos si es demostrable? Para responder que no, Turing necesitaba antes definir con precisión qué es un procedimiento mecánico, y lo hizo pensando en una persona que calcula con lápiz y papel. Esa persona mira unos pocos símbolos, recuerda en qué punto del cálculo está, escribe o borra algo y desplaza la atención. Cada uno de esos gestos se puede reducir a los de la máquina sin perder nada, y por eso en el artículo la palabra computer designa todavía, como era corriente en 1936, a la persona que hace los cálculos.

El paso decisivo del artículo es la máquina universal (universal Turing machine). La tabla de reglas de una máquina se puede escribir como una ristra de símbolos, y esa ristra se puede poner en la cinta de otra máquina. Turing construyó una máquina capaz de leer la descripción de cualquier otra y de imitar su comportamiento paso a paso. Es la idea del programa informático: un único aparato que hace el trabajo de todos los demás si se le da la descripción adecuada. Nueve años después, John von Neumann la convertiría en la arquitectura de los ordenadores reales, con el programa guardado en la misma memoria que los datos.

Con la máquina universal en la mano, la respuesta al problema de Hilbert es un argumento de pocas líneas. Supóngase que existe una máquina que, dada la descripción de cualquier otra y una entrada, dice si esa otra acabará parando o se quedará calculando para siempre. Se construye entonces una máquina tramposa que consulta a la primera sobre sí misma y hace lo contrario de lo que esta predice: si la predicción es que parará, se mete en un bucle infinito, y si es que no parará, se detiene. Ninguna respuesta de la supuesta adivina es correcta, así que la adivina no puede existir. Es lo que hoy se llama el problema de la parada (halting problem), aunque el nombre no es de Turing sino de la década de 1950, y de él se deduce que el problema de la decisión no tiene solución. Alonzo Church había llegado a la misma conclusión unas semanas antes en Princeton, con un formalismo distinto, el cálculo lambda; Turing demostró en un apéndice que los dos formalismos definen exactamente las mismas funciones, y se fue a Princeton a hacer el doctorado con él.

La coincidencia no fue un accidente, y es lo que se conoce como tesis de Church-Turing (Church-Turing thesis): todo lo que se puede calcular mediante un procedimiento efectivo lo calcula una máquina de Turing. No es un teorema, porque «procedimiento efectivo» no es una noción matemática, sino una hipótesis que ha resistido noventa años. Todos los modelos de cálculo propuestos desde entonces, las funciones recursivas, los sistemas de reescritura, los autómatas celulares, cualquier lenguaje de programación real, resultaron equivalentes a ella o más débiles. Cuando se dice que un lenguaje o un sistema es Turing completo (Turing complete), se quiere decir que alcanza ese techo: con memoria suficiente, puede calcular cualquier cosa que calcule un ordenador. Lo son lenguajes pensados para ello como C o Python, y también algunos que nadie diseñó con esa intención, como las fórmulas de una hoja de cálculo moderna, las reglas del juego de la vida de Conway o el sistema de cartas de Magic: The Gathering.

La máquina de Turing no es un modelo de cómo funciona un ordenador; nadie la construye para usarla, y un programa sencillo exige en ella millones de pasos de ir y venir por la cinta. Es una medida de lo que un ordenador puede hacer, y su lección más duradera es negativa. El problema de la parada no es un caso raro: el teorema de Rice, de 1953, generaliza el argumento y muestra que ninguna propiedad no trivial del comportamiento de un programa se puede decidir mecánicamente en todos los casos. Por eso ningún antivirus detecta todo el código malicioso, ningún compilador encuentra todos los errores y ninguna herramienta de depuración garantiza que un programa termina. Las herramientas reales funcionan aceptando que a veces dirán «no lo sé».

Turing volvió a la máquina de verdad durante la guerra, en Bletchley Park, y después en Mánchester, donde escribió el manual de programación de uno de los primeros ordenadores comerciales. Pero el artículo de 1936 se sigue leyendo por otra razón: antes de que existiera un solo ordenador, fijó a la vez qué es calcular y dónde acaba. Cualquier máquina que se construya después, por rápida que sea, vive dentro de ese límite.