Simulador de máquina de Turing

Una máquina de Turing es un modelo matemático formal de computación que consta de una cinta infinita, un cabezal de cinta y una tabla de transición de estados. Define los límites de lo calculable (tesis de Church-Turing). Demuestra la indecidibilidad del problema de la parada, mostrando que ningún algoritmo puede predecir si un programa terminará.

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.

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.