Las máquinas de Turing explicadas
En 1936, antes de que existieran los ordenadores electrónicos, el matemático Alan Turing, de 24 años, se preguntó qué significa que un cálculo sea mecánico. Su respuesta fue una máquina imaginaria tan sencilla que difícilmente podría hacer menos: lee y escribe símbolos en una cinta, una celda cada vez, según una tabla fija de reglas. Esa máquina resultó definir el propio cómputo, y demostró que hay preguntas que ningún ordenador podrá responder jamás.
La pregunta de Turing
En 1928, David Hilbert preguntó si existe un procedimiento mecánico que decida, para todo enunciado matemático, si se puede demostrar: el Entscheidungsproblem. Para responder, alguien tenía que decir exactamente qué es un procedimiento mecánico. En su artículo de 1936 On Computable Numbers, Turing imaginó a un oficinista que trabaja con lápiz y papel, y redujo su trabajo a los pasos más pequeños: mirar un símbolo, cambiarlo, pasar a un símbolo vecino y recordar un poco de lo que estaba haciendo. El resultado fue la máquina de Turing.
La máquina
Una máquina de Turing tiene una cinta dividida en celdas, infinita en ambas direcciones, cada una con un símbolo, normalmente el blanco. Un cabezal está sobre una celda y la máquina se encuentra en uno de un número finito de estados. Una tabla de reglas indica, para cada estado y cada símbolo que el cabezal puede leer, el símbolo que hay que escribir, la dirección del movimiento y el estado siguiente. La máquina aplica una regla en cada paso. Cuando entra en un estado de parada se detiene, y lo que queda en la cinta es su respuesta.
Programas como tablas de reglas
Cada tabla de reglas es un programa. Para sumar 1 a un número binario, la máquina va hasta el extremo derecho del número y luego se mueve a la izquierda convirtiendo los 1 en 0 hasta encontrar un 0 o una celda en blanco, que convierte en 1. Para comprobar si una palabra es un palíndromo, borra el primer símbolo, lo recuerda en su estado, corre hasta el otro extremo y comprueba que el último símbolo coincide, y luego repite. Los programas largos, como uno que multiplica u ordena, se construyen con los mismos pocos tipos de reglas.
La máquina universal
La idea más importante de Turing fue que la propia tabla de reglas puede escribirse en la cinta. Una máquina de Turing universal lee la descripción de cualquier otra máquina y su entrada, y luego la imita paso a paso. Por tanto, una sola máquina fija puede ejecutar cualquier programa: es el principio de todo ordenador de programa almacenado, en el que el software no es más que datos en la memoria. Todo sistema capaz de imitar una máquina de Turing universal se llama Turing completo, incluidos todos los lenguajes de programación, el Juego de la vida de Conway y el autómata celular Rule 110.
La tesis de Church-Turing
Ese mismo año, Alonzo Church describió el cómputo con su cálculo lambda, y resultó que ambas definiciones calculaban exactamente las mismas funciones. Lo mismo ocurrió con todos los modelos posteriores, desde las máquinas de registros hasta los procesadores modernos. La tesis de Church-Turing afirma que todo lo que puede calcularse mediante un procedimiento paso a paso puede calcularlo una máquina de Turing. No se puede demostrar, porque «procedimiento paso a paso» es una idea informal, pero nunca se ha encontrado un contraejemplo.
El problema de la parada
Después, Turing demostró que algunas preguntas no tienen respuesta mecánica. Supongamos que una máquina pudiera decidir, para todo programa y toda entrada, si ese programa acaba deteniéndose. Construyamos un programa nuevo que pregunte a ese decisor sobre sí mismo y luego haga lo contrario: si le dice que se detiene, entra en un bucle infinito, y si le dice que entra en bucle, se detiene. Cualquiera de las dos respuestas es errónea, así que el decisor no puede existir. El problema de la parada es indecidible, y con él el Entscheidungsproblem: ningún algoritmo puede resolver todas las cuestiones matemáticas.
Castores afanosos
En 1962, Tibor Radó convirtió el problema de la parada en un juego: entre todas las máquinas con n estados y los símbolos 0 y 1 que se detienen al ponerlas en marcha sobre una cinta en blanco, ¿cuál escribe la mayor cantidad de unos y cuántos pasos puede dar una máquina así? Estos números, los valores del castor afanoso, crecen más rápido que cualquier función computable, porque una forma de calcularlos resolvería el problema de la parada. Los valores conocidos son 6, 21 y 107 pasos para dos, tres y cuatro estados; para cinco estados, la máquina campeona de Heiner Marxen y Jürgen Buntrock da 47.176.870 pasos, un valor demostrado en 2024 por la colaboración en línea bbchallenge con una demostración verificada por ordenador. Para seis estados se conocen máquinas que funcionan durante más pasos de los que pueden escribirse en notación ordinaria.
Explóralo
Abre el simulador de máquina de Turing para ejecutar ocho programas ya preparados o escribir los tuyos. Sigue el cabezal paso a paso y mira qué regla se aplica, observa el contador que nunca se detiene, comprueba palíndromos y ejecuta los castores afanosos: los 107 pasos de la campeona de cuatro estados caben en el diagrama, y los 47 millones de pasos de la campeona de cinco estados tardan unos segundos a la velocidad Muy rápida.
Preguntas frecuentes
¿Llegó a construirse la máquina de Turing?
No tal como la describió Turing, ya que su cinta es infinita, pero a la idea pronto le siguieron ordenadores reales de programa almacenado, que el propio Turing ayudó a diseñar después de la Segunda Guerra Mundial. Desde entonces, aficionados han construido modelos que funcionan con madera, con LEGO e incluso dentro del Juego de la vida, todos con una cinta finita, lo que basta para cualquier cálculo que termine.
¿Qué diferencia hay entre los recuentos de 14 y 21 pasos para tres estados?
Hay dos preguntas del castor afanoso: la mayor cantidad de unos escritos y la mayor cantidad de pasos dados. Para tres estados, la máquina del simulador escribe el máximo de seis unos en 14 pasos, mientras que otra máquina de tres estados da el máximo de 21 pasos pero deja solo cinco unos. Para dos, cuatro y cinco estados, una misma máquina gana en ambas.
¿Turing completo significa potente?
Significa capaz de calcular todo lo computable, con suficiente tiempo y memoria, lo que no dice nada de la velocidad. Una máquina de Turing necesita muchos pasos para una aritmética sencilla, y algunos sistemas son Turing completos casi por accidente, como juegos de cartas, fórmulas de hojas de cálculo y la redstone de Minecraft.
¿Por qué un ordenador no puede simplemente ejecutar un programa para ver si se detiene?
Ejecutarlo demuestra que un programa se detiene, si lo hace, pero si todavía no se ha detenido no puedes saber si nunca lo hará o si solo necesita más tiempo. La demostración de Turing muestra que ningún método más ingenioso funciona para todos los programas, aunque para muchos programas concretos la pregunta sí tiene respuesta.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Abrir el simulador de máquina de Turing