90 años de la máquina de Turing: la teoría que inventó la computación y el software

Hace exactamente 90 años, Alan Turing envió a ‘Proceedings of the London Mathematical Society’ un manuscrito que definió con precisión qué significa computación y demostró que hay problemas imposibles de resolver por un algoritmo.

El matemático estableció un modelo general de computación y probó que podía existir una máquina capaz de simular cualquier otra. Esa construcción, hoy llamada máquina de Turing universal, es considerada por diferentes expertos como la antepasada conceptual del ordenador y del software.

Turing tenía 23 años y se había graduado en la Universidad de Cambridge un par de años antes. El artículo, titulado “On computable numbers with an application to Entscheidungsproblem”, no solo formuló un modelo abstracto de cálculo, sino que fijó uno de los límites fundamentales de las matemáticas: existen preguntas que ningún procedimiento algorítmico puede contestar.

El matemático definió primero los “números computables” como aquellos cuyos decimales pueden obtenerse mediante un procedimiento bien definido y finito, lo que hoy se llama algoritmo. En ese marco, mostró que constantes como pi y e son computables, pero que existen números reales que no lo son.

La pregunta de fondo era más amplia: cómo formalizar la propia idea de calcular. Para responderla, Turing introdujo lo que hoy se conoce como máquina de Turing, un modelo abstracto que expertos describen como una “impresora” de datos y estados sobre una cinta infinita.

Cómo operaba la máquina de Turing

Esa máquina se sitúa en una posición de la cinta, lee el símbolo presente y, de acuerdo con esa información y con su estado inicial, puede modificar el símbolo, cambiar de estado y desplazarse un paso a la izquierda o a la derecha.

Después repite el mismo proceso en la casilla siguiente hasta llegar a una orden de parada; si nunca la alcanza, el cálculo continúa indefinidamente en un bucle.

La idea tiene una consecuencia concreta: todos los ordenadores programables de uso cotidiano, desde el teléfono hasta el portátil, se apoyan en ese marco teórico, según expertos como Daniel Peralta Salas, profesor de investigación del Consejo Superior de Investigaciones Científicas (CSIC).

Además, no se trata de una máquina física diseñada por Turing, sino de una formulación abstracta que permite pensar cualquier programa como una secuencia de instrucciones ejecutables.

En qué se diferenció la propuesta de Turing de otros matemáticos

David Hilbert había formulado la posibilidad de un algoritmo universal capaz de decidir, en tiempo finito, si cualquier enunciado lógico o matemático es verdadero o falso; en cambio Turing, influido por los teoremas de incompletitud de Kurt Gödel, demostró que ese algoritmo no podía existir.

La prueba se apoyó en un caso particular que acabaría convirtiéndose en una frontera central de la computación: el problema de la parada. Ese problema consiste en determinar, para cualquier algoritmo y cualquier estado inicial, si la ejecución terminará con un resultado o seguirá para siempre en un bucle infinito.

La conclusión de Turing fue que no existe ninguna máquina de Turing capaz de decidir correctamente todos los casos. Por eso, explica Peralta Salas, hoy se dice que el problema de la parada es indecidible.

Asimismo, el alcance de esa demostración no quedó limitado a la lógica matemática. Con los años se han identificado otros problemas indecidibles en ámbitos muy distintos, desde la mecánica newtoniana hasta la mecánica cuántica, la óptica geométrica y la dinámica de fluidos, pero el punto de partida sigue siendo el problema resuelto por Turing en la década de los 30.

Cuál es el legado de Alan Turing

Expertos señalan que ese trabajo fue solo una contribución dentro de una trayectoria repleta de aportes fundamentales, pero es suficiente para medir la deuda de la sociedad contemporánea con el legado matemático de Turing.

La dimensión de esa obra contrasta con el final del científico: dos años después de ser condenado y sometido a castración química por ser homosexual en Gran Bretaña, donde esa condición fue delito hasta 1967, murió por ingesta de cianuro a los 41 años.