Cuando inventó las máquinas de Turing en 1936 Alan Turing también inventó la informática moderna.

Un artículo de Sheon Han. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

La computación es un concepto familiar que la mayoría de nosotros entendemos intuitivamente. Toma la función f(x) = x + 3. Cuando x es tres, f(3) = 3 + 3. Seis. Fácil. Parece obvio que esta función es computable. Pero algunas funciones no son tan simples y no es tan fácil determinar si se pueden calcular, lo que significa que es posible que nunca nos den una respuesta final.

En 1928, los matemáticos alemanes David Hilbert y Wilhelm Ackermann propusieron una pregunta llamada el Entscheidungsproblem (“problema de decisión”). Con el tiempo, su pregunta conduciría a una definición formal de computabilidad, que permitió a los matemáticos responder a una serie de nuevos problemas y sentó las bases para la informática teórica.

La definición provino de un estudiante de posgrado de 23 años llamado Alan Turing, quien en 1936 escribió un artículo fundamental que no solo formalizó el concepto de computación, sino que también demostró una pregunta fundamental en matemáticas y creó la base intelectual para la invención del ordenador electrónico. La gran idea de Turing fue proporcionar una respuesta concreta a la cuestión de la computación en forma de una máquina abstracta, más tarde denominada máquina de Turing por su director de tesis, Alonzo Church. Es abstracta porque no existe (y no puede existir) físicamente como un dispositivo tangible. En cambio, es un modelo conceptual de computación: si la máquina puede calcular una función, entonces la función es computable.

Así es como funciona. Una máquina de Turing puede leer y alterar símbolos en una cinta infinitamente larga, siguiendo una tabla de reglas. La cinta se compone de «celdas», cada una de las cuales puede almacenar exactamente un símbolo, y la máquina lee y reescribe el contenido de las celdas con un cabezal magnético. Cada regla de la tabla determina lo que debe hacer la máquina según su estado actual y el símbolo que está leyendo. La máquina puede entrar en un estado final («estado de aceptación» o «estado de rechazo») en el que se detiene, aceptando o rechazando la entrada. O cae en un bucle infinito y continúa leyendo la cinta para siempre.

La mejor manera de entender una máquina de Turing es considerar un ejemplo simple. Imaginemos uno que está diseñado para decirnos si una entrada determinada es el número cero. Usaremos el número de entrada 0001 acompañado de almohadillas (#), por lo que “#0001#” es la parte relevante de nuestra cinta.

La máquina arranca en el estado inicial, al que llamaremos q0. Lee la celda más a la izquierda de nuestra cinta y encuentra una almohadilla. Las reglas dicen: «Cuando estés en el estado q0, si el símbolo es #, déjalo como está sin modificaciones, muévete una celda a la derecha y cambia el estado de la máquina a q1». Después de este paso, la máquina está en el estado q1, y su cabezal lee el segundo símbolo, 0.

Ahora buscamos una regla que se aplique a estas condiciones. Encontramos una que dice: «Permanece en el estado q1 y mueve el cabezal una celda a la derecha». Esto nos deja en la misma posición (en el estado q1, leyendo “0”), así que seguimos moviéndonos hacia la derecha hasta que el cabezal finalmente lee un número diferente, el 1.

Cuando volvemos a consultar la tabla, encontramos una nueva regla: «Si encontramos un 1, pasa a q2, que es un estado de ‘rechazo'». La máquina se detiene y responde «No» a la pregunta original: «¿Es ‘0001’ cero?»

Si, en cambio, la entrada es «#0000#», la máquina encontrará un # después de todos esos ceros. Cuando consultamos la tabla, encontramos una regla que dice que esto significa que la máquina entra en el estado q3, un estado de «aceptación». Ahora la máquina responde «Sí» a la pregunta «¿Es ‘0000’ cero?»

Con su máquina abstracta Turing estableció un modelo de computación para responder al Entscheidungsproblem, que pregunta formalmente: dado un conjunto de axiomas matemáticos, ¿existe un proceso mecánico (un conjunto de instrucciones, lo que hoy llamaríamos un algoritmo) que siempre puede determinar si una afirmación dada es verdadera?

Digamos que queremos encontrar un algoritmo que pueda decirnos si una cierta posición de ajedrez es posible. Aquí, los axiomas son las reglas del ajedrez que gobiernan los movimientos legales. ¿Podemos seguir una secuencia finita de procedimientos paso a paso para llegar a esa posición? Aunque algunas posiciones pueden tardar más de una vida en analizarse (un algoritmo puede generar todas las posiciones posibles y comparar cada una de ellas con la entrada), algoritmos así existen en el juego de ajedrez. Como resultado, decimos que el ajedrez es «decidible».

Sin embargo, en 1936, Church y Turing —usando diferentes métodos— demostraron de forma independiente que no existe una forma general de resolver cada instancia del Entscheidungsproblem. Por ejemplo, algunos juegos, como el “Juego de la vida” de John Conway, son indecidibles: ningún algoritmo puede determinar si un cierto patrón aparecerá a partir de un patrón inicial.

Turing demostró que una función es computable si existe un algoritmo que puede ejecutar la tarea deseada. Al mismo tiempo, demostró que un algoritmo es un proceso que puede ser definido por una máquina de Turing. Por lo tanto, una función computable es una función que tiene una máquina de Turing para calcularla. Esto puede parecer una forma enrevesada de definir la computabilidad, pero es la mejor que tenemos. “No es como si tuvieras la opción de definirlo de otra manera”, afirma Michael Sipser, informático teórico del Instituto de Tecnología de Massachusetts. «Creo que se acepta comúnmente que la tesis de Church-Turing dice que la noción informal de algoritmo corresponde a lo que puede hacer cualquier modelo computacional ‘razonable'». Otros matemáticos han ideado diferentes modelos de cálculo que parecen bastante diferentes en la superficie pero que en realidad son equivalentes: pueden hacer cualquier cálculo que las máquinas de Turing puedan hacer, y viceversa.

Solo unos años después de que Kurt Gödel demostrara que las matemáticas eran incompletas, Church y Turing demostraron con este trabajo que algunos problemas matemáticos son indecidibles: ningún algoritmo, por sofisticado que sea, puede decirnos si la respuesta es sí o no. Fueron ambos golpes devastadores para Hilbert, quien esperaba que las matemáticas tuvieran respuestas ordenadas e idealizadas. Pero tal vez sea mejor así: si existiera una solución general al Entscheidungsproblem, significaría que todos los problemas matemáticos podrían reducirse a simples cálculos mecánicos.

Más allá de responder a estas preguntas fundamentales, la máquina de Turing también condujo directamente al desarrollo de los ordenadores modernos a través de una variante conocida como máquina universal de Turing. Este es un tipo especial de máquina de Turing que puede simular cualquier otra máquina de Turing en cualquier entrada. Puede leer una descripción de otras máquinas de Turing (sus reglas y cintas de entrada) y simular sus comportamientos en su propia cinta de entrada, produciendo el mismo resultado que produciría la máquina simulada, al igual que los ordenadores actuales pueden leer cualquier programa y ejecutarlo. En 1945, John von Neumann propuso una arquitectura de ordenador, llamada arquitectura de von Neumann, que hizo posible el concepto de máquina universal de Turing en una máquina real.

Cuando Sanjeev Arora, informático teórico de la Universidad de Princeton, enseña este concepto, enfatiza una imagen filosófica más amplia. «Hay dos nociones de ‘universal'», explica. “Una noción de lo universal es que puede hacer funcionar cualquier otra máquina de Turing. Pero la otra noción mayor de ‘universal’ es que puede ejecutar cualquier cálculo que se te ocurra en el universo». En el mundo de la física clásica, cualquier proceso físico se puede modelar o simular mediante algoritmos que, a su vez, se pueden simular mediante una máquina de Turing.

Otra variante notable y cada vez más útil es la máquina de Turing probabilística. A diferencia de una máquina de Turing normal, que tiene una reacción bien definida para cada entrada, una máquina de Turing probabilística puede tener múltiples reacciones basadas en probabilidades. Esto significa que puede producir diferentes resultados para la misma entrada en diferentes momentos. Sorprendentemente, este tipo de estrategia probabilística puede ser más eficiente que un enfoque puramente determinista para ciertos problemas. Se ha demostrado que las ideas de las máquinas de Turing probabilísticas son útiles en la práctica en áreas como la criptografía, la optimización y el aprendizaje automático.

Estas máquinas abstractas son quizás la mejor prueba de que hacer preguntas fundamentales puede ser una de las cosas más útiles que puede hacer un científico.

El artículo original, The Most Important Machine That Was Never Built, se publicó el 3 de mayo de 2023 en Quanta Magazine.

Traducido por César Tomé López