Simulador de máquina de Turing

Observa cómo una máquina de Turing lee, escribe y se desplaza a lo largo de una cinta infinita siguiendo reglas de transición.

Ejemplo resuelto — Simulador de máquina de Turing

Leer	'0'
Posición del cabezal	0

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Una sola cinta vuelve cuadráticos los palíndromos 🖖

El ejemplo del palíndromo acepta 1,0,1,0,1 en 21 pasos y rechaza 1,0,1,1 en 13. La máquina no puede comparar los dos extremos a la vez, así que borra el símbolo más a la izquierda, lo lleva en su estado, recorre toda la cinta para comprobar el de más a la derecha, lo borra y vuelve caminando, una vez por pareja. Para una cinta de n unos, este programa emplea exactamente (n+1)(n+2)/2 pasos: 21 con n = 5, 55 con n = 9, 253 con n = 21. Dale a la misma máquina una segunda cinta y la tarea se vuelve lineal; Hennie demostró en 1965 que con una sola cinta no puede serlo. El coste no está en el alfabeto ni en el número de estados: está en el caminar.

Cómo unas pocas reglas lo ejecutan todo 🖖

Una máquina de Turing casi no tiene nada: una cinta, un cabezal que lee una celda y una breve tabla de reglas. En cada paso solo mira su estado actual y el símbolo bajo el cabezal; luego escribe un símbolo, se mueve una celda a izquierda o derecha y cambia de estado. Ejecuta el preajuste de incremento binario y observa cómo se desliza hasta el final y arrastra el +1 de vuelta hacia la izquierda, igual que cuando sumas a mano.

El castor atareado supera al universo 🖖

Haz la pregunta más pequeña —¿cuánto puede correr una máquina diminuta antes de detenerse?— y el cálculo explota. Una máquina de 5 estados y 2 símbolos avanza exactamente 47,176,870 pasos antes de parar, un valor demostrado apenas en 2024. Con 6 estados, el récord conocido ya supera 2↑↑↑5, una torre de potencias que empequeñece a cada átomo del cosmos. Por eso los simuladores como este limitan cada ejecución: un puñado de estados puede sobrevivir a la eternidad.

Problema resuelto al detalle

Configuraciones por las que pasa el programa de palíndromos con 1 0 1 0 1 5 pasos
El programa palíndromo comienza en la cinta 1 0 1 0 1, con el cabezal en la celda 0, estado q0. Cuente cada configuración por la que pasa antes de detenerse —a partir de la tabla de reglas, sin ejecutar paso a paso— y luego diga qué hace ese recuento a medida que la entrada se vuelve más larga.
1. Lea la tabla como rondas, no como una lista de movimientos. Solo una regla puede abrir una ronda: q0 borra el símbolo situado más a la izquierda y se ramifica según lo que acaba de borrar, a q1 para un 1 y a q2 para un 0. Esa ramificación es todo el mecanismo de comparación. La máquina nunca almacena el símbolo en la cinta; lo almacena en el estado en el que se encuentra, por lo que comprobar el extremo opuesto con él más tarde no requiere movimientos adicionales.
  
  $q_{0} : 1 \mapsto (_, R, q_{1}), 0 \mapsto (_, R, q_{2})$
2. Cuente una ronda en un bloque de m símbolos. Borrar el extremo izquierdo es 1 movimiento. El cabezal cruza entonces los m − 1 símbolos que aún quedan y dedica 1 movimiento más a la casilla en blanco situada más allá de ellos para darse la vuelta. Borrar el extremo derecho es 1 movimiento, recorrer de vuelta los m − 2 supervivientes son m − 2 movimientos, y 1 último movimiento en la casilla en blanco del extremo izquierdo vuelve a orientar a la máquina a la derecha en q0.
  
  $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$
3. Nuestra cinta ofrece un bloque de 5, luego 3, luego un único símbolo, y un único símbolo no es una ronda. q0 lo borra, q1 sale por el extremo derecho y se gira, y q1c encuentra un blanco donde debería estar su pareja. Un palíndromo de longitud impar tiene un centro no emparejado, y encontrar ese blanco es lo que hace que se acepte.
  
  $m = 5 : 11, m = 3 : 7, m = 1 : 3$
4. Sume los tres y tenga en cuenta el poste de la cerca. 21 es el número de movimientos; el transporte cuenta configuraciones, y 21 movimientos visitan 22 de ellas una vez incluida aquella en la que se empezó.
  
  $11 + 7 + 3 = 21 ⟹ 21 + 1 = 22$
5. Generalice a cualquier longitud impar n. Los bloques van descendiendo n, n − 2 y así sucesivamente hasta 3, cada uno con un coste de 2m + 1, y con el centro costando 3. Sumar esa lista da una expresión cuadrática en n, no lineal.
  
  $(2 n + 1) + (2 n - 3) + \dots + 7 + 3 = \frac{( n + 1 ) ( n + 2 )}{2}$
Respuesta

22 configuraciones — 21 movimientos. El comportamiento cuadrático es lo que conviene conservar. Un palíndromo de 21 símbolos cuesta 253 movimientos: 12 veces el trabajo para una entrada 4,2 veces más larga. La razón es geométrica antes que ingeniosa: los dos símbolos que se comparan siempre se encuentran en extremos opuestos de lo que queda y solo hay un cabezal, por lo que cada par cuesta un recorrido completo de la cinta restante. Si se le da a la máquina una segunda cinta, el mismo trabajo pasa a ser lineal: copiar la entrada a medida que se lee, luego hacer funcionar los dos cabezales en direcciones opuestas y comparar en una sola pasada, aproximadamente 3n movimientos. En una sola cinta no hay lugar donde colocar esa copia, y el vaivén resulta inevitable.

$n = 5 : 21; n = 21 : \frac{22 \cdot 23}{2} = 253$

Referencias (3)

The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.

Por el equipo de 42Math · Actualizado 2026-06-19

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

Invertir bits - Inversión de bits: intercambia 0 y 1
Binario +1 - Incremento binario: 1011→1100
1111 → 10000 - Aquí tienes el peor escenario posible al incrementar la entrada: cada bit es un 1, por lo que el acarreo tiene que invertirlos todos. Fíjate cómo avanza hacia la derecha hasta el espacio en blanco. Luego retrocede a la izquierda, convierte cada 1 en un 0 y escribe un 1 inicial en una celda ajena a la entrada. Son once configuraciones en total. La cinta regresa midiendo una celda más de lo que entró.
Suma unaria m+n - Suma unaria: 3+2=5
1+1 = 2 - Es la suma unaria más sencilla posible y, aun así, necesita nueve configuraciones. La máquina no sabe sumar. Borra un 1 del bloque izquierdo, recorre toda la cinta y añade un 1 a la derecha, una vez por cada unidad. El coste crece según la magnitud de los números, no por la longitud de su notación. Carga el ejemplo unario más largo y cuenta la diferencia.
Palíndromo ✓ - Verificador de palíndromos: 10101
1011 — rechazado - Los extremos coinciden: la cadena empieza y termina con un 1. La máquina borra ambos y regresa para evaluar el interior. Solo entonces encuentra un 0 frente a un 1 y pasa al estado de rechazo, mientras el visor indica la regla responsable. Comprobar un palíndromo con una cinta única no permite detectar el fallo de forma anticipada. Esa es exactamente la razón por la que requiere un recorrido completo por cada par.

YouTube

The Rest Is Science·Alan Turing's Final Theory Was About Leopards