Simulador de Máquina de Turing

Observe uma máquina de Turing ler, escrever e se mover ao longo de uma fita infinita seguindo regras de transição.

Exemplo resolvido — Simulador de Máquina de Turing

Ler	'0'
Posição da cabeça	0

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Uma única fita torna palíndromos quadráticos 🖖

O exemplo do palíndromo aceita 1,0,1,0,1 em 21 passos e rejeita 1,0,1,1 em 13. A máquina não consegue comparar as duas pontas ao mesmo tempo, então apaga o símbolo mais à esquerda, carrega-o em seu estado, caminha por toda a fita para conferir o mais à direita, apaga esse e volta caminhando — uma vez por par. Para uma fita de n uns, este programa leva exatamente (n+1)(n+2)/2 passos: 21 com n = 5, 55 com n = 9, 253 com n = 21. Dê à mesma máquina uma segunda fita e a tarefa se torna linear; Hennie provou em 1965 que com uma única fita ela não pode ser. O custo não está no alfabeto nem no número de estados — está na caminhada.

Como poucas regras executam tudo 🖖

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.

O castor ocupado supera o universo 🖖

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.

Problema resolvido na íntegra

Configurações pelas quais o programa do palíndromo passa em 1 0 1 0 1 5 passos
O programa de palíndromos começa na fita 1 0 1 0 1, com a cabeça na célula 0, no estado q0. Conte todas as configurações pelas quais passa antes de parar — a partir da tabela de regras, sem o executar passo a passo — e depois diga o que acontece a essa contagem à medida que a entrada aumenta de comprimento.
1. Leia a tabela em termos de rondas, e não como uma lista de movimentos. Apenas uma regra pode abrir uma ronda: q0 apaga o símbolo mais à esquerda e desvia em função do que acabou de apagar, para q1 para um 1 e para q2 para um 0. Esse desvio é todo o mecanismo de comparação. A máquina nunca guarda o símbolo na fita; guarda-o no estado em que se encontra, pelo que testar a extremidade oposta contra ele mais tarde não custa movimentos adicionais.
  
  $q_{0} : 1 \mapsto (_, R, q_{1}), 0 \mapsto (_, R, q_{2})$
2. Conte uma ronda num bloco de m símbolos. Apagar a extremidade esquerda é 1 movimento. A cabeça atravessa então os m − 1 símbolos que ainda restam e gasta mais 1 movimento no espaço em branco além deles para dar a volta. Apagar a extremidade direita é 1 movimento, regressar sobre os m − 2 sobreviventes são m − 2 movimentos, e 1 último movimento no espaço em branco na extremidade esquerda volta a virar a máquina para a direita em q0.
  
  $1 + (m - 1) + 1 + 1 + (m - 2) + 1 = 2 m + 1$
3. A nossa fita dá um bloco de 5, depois 3, e depois um único símbolo — e um único símbolo não é uma ronda. q0 apaga-o, q1 sai pela extremidade direita e vira-se, e q1c encontra um espaço em branco onde deveria estar um par. Um palíndromo de comprimento ímpar tem um centro sem par, e encontrar esse espaço em branco é o que faz aceitar.
  
  $m = 5 : 11, m = 3 : 7, m = 1 : 3$
4. Some os três e tenha em atenção o problema dos postes de vedação. 21 é o número de movimentos; o transporte conta configurações, e 21 movimentos visitam 22 delas, uma vez incluída aquela em que começou.
  
  $11 + 7 + 3 = 21 ⟹ 21 + 1 = 22$
5. Generalize para qualquer comprimento ímpar n. Os blocos vão de n, n − 2, e assim sucessivamente até 3, custando cada um 2m + 1, com o centro a custar 3. A soma dessa lista dá uma função quadrática em n, e não uma linear.
  
  $(2 n + 1) + (2 n - 3) + \dots + 7 + 3 = \frac{( n + 1 ) ( n + 2 )}{2}$
Resposta

22 configurações — 21 movimentos. O comportamento quadrático é a parte que vale a pena reter. Um palíndromo de 21 símbolos custa 253 movimentos: 12 vezes o trabalho para uma entrada 4,2 vezes mais longa. A razão é geométrica e não por astúcia — os dois símbolos a serem comparados situam-se sempre em extremidades opostas do que resta, e há apenas uma cabeça, pelo que cada par custa uma travessia completa da fita restante. Dê à máquina uma segunda fita e o mesmo trabalho torna-se linear: copie a entrada enquanto a lê, depois execute as duas cabeças em direções opostas e compare numa única passagem, cerca de 3n movimentos. Numa só fita não há onde colocar essa cópia, e o movimento de vaivém é inevitável.

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

Referências (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.

Pela equipa 42Math · Atualizado 2026-06-19

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

Inverter bits - Inversão de bits: troca 0s por 1s
Binário +1 - Incremento binário: 1011→1100
1111 → 10000 - O incremento recebe a pior entrada possível: cada bit é um 1, de modo que o transporte precisa inverter todos eles. Observe a máquina avançar à direita até o espaço em branco. Ela retorna à esquerda transformando cada 1 num 0 e, em seguida, grava um novo 1 inicial numa célula que nunca fez parte da entrada. São onze configurações ao todo, e a fita retorna uma célula mais longa do que quando entrou.
Soma unária m+n - Adição unária: 3+2=5
1+1 = 2 - A soma unária mais simples de todas, e ainda assim requer nove configurações. A máquina não consegue somar. Ela apaga um 1 do grupo da esquerda, percorre toda a fita e anexa um 1 à direita, uma vez por unidade. O custo aumenta com a magnitude dos números, não com o comprimento da notação. Carregue a predefinição unária mais longa e conte a diferença.
Palíndromo ✓ - Verificador de palíndromo: 10101
1011 — rejeitado - O par externo coincide. Como a cadeia começa e termina com um 1, a máquina apaga ambos e retorna à camada interna. Somente lá ela depara com um 0 diante de um 1 e transita para o estado de rejeição. A leitura nomeia a regra responsável. Uma verificação de palíndromos com fita única não tem como falhar precocemente. É exatamente por isso que cada par exige uma varredura completa.

YouTube

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