Simulador de Máquina de Turing

Uma máquina de Turing é um modelo matemático formal de computação que consiste numa fita infinita, uma cabeça de leitura e uma tabela de transição. Define os limites do calculável (tese de Church-Turing). Demonstra a indecidibilidade do problema da paragem, provando que nenhum algoritmo pode prever se um programa terminará.

Uma máquina de Turing quase não tem nada: uma fita, um cabeçote que lê uma célula e uma pequena tabela de regras. A cada passo ela olha apenas para o estado atual e o símbolo sob o cabeçote; então escreve um símbolo, move-se uma célula à esquerda ou à direita e muda de estado. Execute a predefinição de incremento binário e veja-a deslizar até o fim e levar o +1 de volta para a esquerda — igual a somar no papel.

Faça a menor pergunta — quanto tempo uma máquina minúscula pode rodar antes de parar? — e o cálculo explode. Uma máquina de 5 estados e 2 símbolos avança exatamente 47,176,870 passos antes de parar, um valor provado apenas em 2024. Com 6 estados, o recorde conhecido já ultrapassa 2↑↑↑5, uma torre de potências que ofusca cada átomo do cosmos. É por isso que simuladores como este limitam cada execução: um punhado de estados pode sobreviver à eternidade.