El 28 de mayo de 1936 la prestigiosa revista británica Proceedings of the London Mathematical Society recibió un manuscrito titulado “On computable numbers with an application to Entscheidungsproblem”. El autor era un matemático de 23 años, graduado por la Universidad de Cambridge un par de años antes, llamado Alan Mathison Turing. Aunque el joven Turing ya había dado muestras de su talento matemático (sus compañeros del colegio ya le llamaban “Mr. Brain”), pocos podían imaginar que ese trabajo (que se publicó el 12 de noviembre de ese mismo año) establecería los cimientos de la informática moderna.
En él, Turing introdujo de manera precisa el concepto de computación para demostrar uno de los límites fundamentales de las matemáticas: que existen problemas (en matemáticas y lógica) que no pueden resolverse mediante un proceso algorítmico. En primer lugar, definió los “números computables” como aquellos cuyos decimales pueden obtenerse mediante un procedimiento bien definido y finito, lo que hoy llamamos un algoritmo. Como ejemplo, demostró que constantes como pi y e son computables, pero que existen números reales que no lo son. Esto le llevó a una pregunta más profunda: ¿qué significa exactamente “computar”? ¿Cómo formalizar la noción misma de cálculo?
Para responderla, introdujo el modelo de lo que hoy en día se conoce como máquina de Turing, la versión abstracta de un programa informático. Una máquina de Turing puede entenderse como una “impresora” de datos (ceros y unos) y estados sobre una cinta infinita. La máquina se sitúa en cierta posición de la cinta y, a partir de sus instrucciones de funcionamiento, realiza una serie de acciones. En primer lugar, lee el símbolo de la posición de la cinta dónde está y, según esta información y su estado de partida, modifica o no el símbolo, cambia su estado a uno nuevo y se mueve un paso hacia la izquierda o la derecha. A continuación, repite el mismo proceso, en la siguiente casilla. Así, la máquina continúa calculando hasta encontrar una orden que la lleve al estado de parada, en el que la máquina se detiene y el cálculo concluye. Si nunca alcanza este estado, el algoritmo entra en bucle y continúa indefinidamente.
Turing entendió la computación como cualquier proceso que puede ser ejecutado (o simulado) mediante una máquina de Turing. En el mismo artículo, analizó la posibilidad de que hubiera una máquina que pudiera realizar “todos los cálculos posibles”, o en otras palabras, una máquina que pudiera simular el comportamiento de cualquier otra máquina de Turing. El científico probó la existencia de dicha máquina, que hoy conocemos como máquina de Turing universal (realmente se pueden construir muchas, unas más simples y eficientes que otras), la cual es considerada como la antepasada conceptual del ordenador y del software. Es decir, todos los ordenadores programables que usamos a diario, desde el móvil hasta el portátil, se fundamentan en estas ideas teóricas.
Los logros anteriores ya hubieran sido suficientes para que el trabajo de Turing de 1936 pasara a la posteridad y, sin embargo, aún falta la cuestión central del artículo: la aplicación de estos conceptos al Entscheidungsproblem (el problema de la decisión). Se trata de una pregunta formulada por el célebre matemático David Hilbert, que planteaba la existencia de un algoritmo “universal” que fuera capaz de determinar, en tiempo finito, si cualquier enunciado lógico o matemático dado es verdadero o falso. Haciendo uso de su máquina, Turing demostró (influenciando por los famosos teoremas de incompletitud de Godel) que no podía existir un algoritmo de ese tipo, destruyendo así el sueño de Hilbert.
Turing mostró que no puede existir un algoritmo capaz de resolver un problema específico: el problema de la parada. Este consiste en determinar, para cualquier algoritmo y cualquier estado inicial, si su ejecución terminará produciendo un resultado o si, por el contrario, continuará indefinidamente, en un bucle infinito. Turing demostró que no hay ninguna máquina de Turing capaz de tomar esa decisión en todos los casos. Por eso, hoy decimos que el problema de la parada es indecidible. Con los años, muchos otros problemas, en contextos muy dispares (desde la mecánica newtoniana hasta la mecánica cuántica, pasando por la óptica geométrica o la dinámica de los fluidos), se han demostrado indecidibles, pero el punto de partida siempre es el famoso problema de la parada resuelto por Turing en 1936.
Aquel trabajo —solo uno dentro de una carrera repleta de contribuciones fundamentales— hace que la deuda de la sociedad contemporánea con el legado matemático de Alan Turing sea indiscutible. Sin embargo, la trascendencia de su obra contrasta con el triste e injusto final del matemático. Dos años después de ser condenado y sometido a castración química por ser homosexual (lo que era considerado un crimen en Gran Bretaña hasta 1967), falleció por ingesta de cianuro, a los 41 años.
Daniel Peralta Salas es profesor de investigación del Consejo Superior de Investigaciones Científicas (CSIC) en el Instituto de Ciencias Matemáticas (ICMAT).
Dimensión fractal es un espacio del Instituto de Ciencias Matemáticas (CSIC-UAM-UC3M-UCM) en el que se ofrece una mirada matemática de la actualidad de la mano de personal investigador especializado.
Edición y coordinación: Ágata Timón García-Longoria, coordinadora de la Unidad de Cultura Científica del ICMAT