Este simulador de máquina de Turing mostra a fita, a posição da cabeça, o estado atual e a regra que está sendo aplicada em cada passo. Você pode usar os exemplos prontos ou escrever a sua própria máquina, como em uma aula de teoria da computação ou linguagens formais.
Partes de uma Máquina de Turing
- Fita: sequência infinita de células, cada uma com um símbolo (ou branco, representado por _).
- Cabeça de leitura e escrita: fica sobre uma célula, lê o símbolo e pode escrever outro.
- Estados: a “memória” da máquina sobre em que etapa do algoritmo ela está.
- Função de transição: a tabela de regras (estado, símbolo lido) → (novo estado, símbolo escrito, movimento).
Como Escrever um Programa no Simulador
Cada linha é uma regra com 5 partes, separadas por espaço:
estado lido novo_estado escreve movimento
inicio 1 inicio 1 D
inicio _ soma _ EO movimento é D (direita), E (esquerda) ou P (parado). O primeiro estado do programa é o estado inicial. A máquina para quando não encontra regra para a situação atual. Estados chamados “aceita” e “rejeita” ficam coloridos para facilitar exercícios de reconhecimento de linguagens.
Exemplo: Somar 1 em Binário
A máquina anda para a direita até passar o último dígito, volta uma casa e soma 1: cada 1 vira 0 e o vai um continua para a esquerda; o primeiro 0 (ou branco) vira 1 e a máquina para. Com a fita 1011 (11), o resultado é 1100 (12) em 8 passos.
Alan Turing e a Computação
Turing propôs a máquina em 1936, no artigo “On Computable Numbers”, para responder se existe um procedimento mecânico capaz de decidir qualquer afirmação matemática. Ele provou que não existe: o problema da parada é indecidível. Na mesma época, o conceito de máquina universal, que lê outra máquina na fita e a simula, antecipou a ideia de programa armazenado usada em todos os computadores atuais. Turing também criou um dos primeiros algoritmos de xadrez, o Turochamp.
Perguntas Frequentes
O que é uma máquina de Turing?
É um modelo matemático de computador criado por Alan Turing em 1936. Ela tem uma fita infinita dividida em células, uma cabeça que lê e escreve um símbolo por vez e uma tabela de regras. Apesar de simples, consegue executar qualquer algoritmo que um computador moderno executa.
Como funciona cada regra da máquina?
Cada regra diz: se estou no estado X e leio o símbolo S, então escrevo o símbolo W, movo a cabeça para a direita, esquerda ou fico parado, e passo para o estado Y. Quando não existe regra para o estado e o símbolo atuais, a máquina para.
Para que serve a máquina de Turing hoje?
Ela define o que é computável. Se um problema não pode ser resolvido por uma máquina de Turing, nenhum computador consegue resolvê-lo. Também é usada para classificar problemas por dificuldade (P, NP) e para provar limites, como a indecidibilidade do problema da parada.
O que é o castor ocupado (busy beaver)?
É o desafio de encontrar a máquina com n estados que escreve o maior número de 1 em uma fita vazia e ainda assim para. Com 3 estados, o recorde é 6 uns. O valor cresce tão rápido que, a partir de poucos estados, não pode ser calculado.
Qual a relação entre a máquina de Turing e o filme O Jogo da Imitação?
O filme conta o trabalho de Alan Turing quebrando a cifra da máquina Enigma na Segunda Guerra. A máquina de Turing é anterior: é o conceito teórico de 1936 que fundou a ciência da computação.