Guia Didático & Manual da MT

Teoria da Computação — Máquinas de Turing na Prática (Prof. Luciano Rovanni)

Abrir Simulador→
🧠

1. Por que precisamos de uma fita?

O Autômato Finito lembra apenas pelo estado. O Autômato com Pilha ganha uma memória, mas só acessa o topo dela. Algumas linguagens exigem mais, como aⁿbⁿcⁿ ou ww: é preciso voltar, comparar e reescrever.

A ideia de Turing Uma fita infinita para os dois lados, dividida em células, e um cabeçote que, a cada passo, lê uma célula, escreve nela e se move uma posição. Como a fita pode ser reescrita e percorrida em qualquer direção, a MT é o modelo mais geral de computação que conhecemos.

Mudança importante de perspectiva: aqui a entrada já está escrita na fita. A máquina não "consome" símbolos, ela os visita.

📐

2. A Definição Formal (A 7-Tupla)

M = (Q, Σ, Γ, δ, q₀, B, F)
Q — conjunto finito de estados.
Σ — alfabeto de entrada (não contém o branco B: o simulador avisa se você tentar usá-lo).
Γ — alfabeto da fita, com Σ ⊆ Γ e B ∈ Γ. Guarda marcas auxiliares como X e Y.
B — símbolo branco (B ∈ Γ, B ∉ Σ). Na digitação, _ também vale.
δ — função de transição parcial: Q × Γ → Q × Γ × {L, R, S}.
q₀, F — estado inicial e conjunto de estados de aceitação.
⚙️

3. Como Funcionam as Transições (δ)

Cada regra tem a forma δ(q, a) = (p, b, D) e é lida assim: "no estado q lendo a, vá para p, escreva b e mova o cabeçote para D". No diagrama, o rótulo da seta aparece como a → b,D.

R
direita
L
esquerda
S
fica no lugar
Exemplo (aⁿbⁿ):
δ(q₀, a) = (q₁, X, R)  → marca o primeiro a com X e vai procurar um b
δ(q₁, b) = (q₂, Y, L)  → marca o b com Y e volta
Técnica central — marcar e voltar: a MT troca símbolos já tratados por marcas (X, Y) para saber "onde parou". É assim que ela conta sem pilha.
🛑

4. Parada e Aceitação

Diferente dos autômatos anteriores, a MT pode nunca parar. Há três desfechos possíveis:

Aceita
Para em estado de aceitação.
Rejeita
Para sem aceitar, por não haver regra aplicável.
Não para
Entra em laço infinito. O simulador interrompe após 250 passos.

O campo Modo de aceitação escolhe a convenção:

Estado de rejeição (qr): como na aula, você pode marcar um estado como de rejeição (botão direito → "Alternar rejeição", ou no editor do estado). Ele aparece com anel tracejado vermelho: ao chegar nele a máquina para e rejeita. Sem um qr, a rejeição acontece por falta de regra aplicável. Veja o exemplo 0ⁿ1ⁿ (aula), com qa e qr explícitos.
Por que isso importa: como a MT pode não parar, o problema da parada é indecidível. Teste o exemplo Loop ∞ e observe: "não parou em 250 passos" não prova que nunca vai parar.
🌿

5. Determinismo e Ramais (MTN)

Se existir mais de uma regra para o mesmo par (estado, símbolo), a máquina é não determinística (MTN). O selo no painel de análise muda de MTD para MTN. A cada escolha, o simulador cria um ramo de computação. A MTN aceita se algum ramo aceitar.

Resultado fundamental: MTN e MTD reconhecem exatamente as mesmas linguagens. A MTN pode ser mais conveniente de projetar, mas não é mais poderosa. Abra o exemplo MTN e clique nos ramos em Configurações Ativas para ver cada fita separadamente.
📚

6. Exemplos Prontos

aⁿbⁿ — marca um a e um b por rodada (entrada padrão: aabb).
0ⁿ1ⁿ (aula) — a máquina do slide: marca um 0 com x e um 1 com y por rodada, com qa e qr explícitos (entrada padrão: 0011).
Palíndromo — compara a primeira e a última letra, apaga ambas e repete.
Soma unária — transforma 11+111 em 11111, apagando o "+".
Cópia — transdutor: a fita passa de w para w#w, mostrando que a MT também calcula funções.
MTN — "adivinha" um a na entrada e aceita se existir ao menos um (ramos que apostam errado morrem).
Loop ∞ — vai e volta para sempre, ilustrando uma computação que não para.
🖱️

7. Guia Rápido de Interação

Duplo clique no vazio:cria um estado.
Duplo clique no estado:alterna estado de aceitação.
Arrastar um estado:move o estado (Ctrl+Z desfaz).
Arrastar o fundo:move a câmera.
Shift + arrastar entre estados:cria uma regra δ (ou use o botão "Criando Transições").
Clique na seta:edita a regra.
Botão direito:menu do estado, da seta ou do fundo (inclui laço e duplicar regra).
Roda do mouse:zoom.

Organizando o diagrama e acompanhando a execução

Círculo / Linha / Grade:organizam os estados automaticamente.
Centralizar:enquadra a máquina na tela.
▶ Play / ◀ ▶ / ⏮ ⏭:reproduz, volta e avança passos da computação.
Clique numa linha do Rastreamento:salta até aquele passo.
Configuração (⊢):cada passo mostra a descrição instantânea, com o estado antes do símbolo lido (ex.: X X q₁ y 1).
Linha da tabela em destaque:a regra aplicada no passo atual fica marcada na tabela de δ.
Arrastar a fita:role a fita com o mouse; ela acompanha o cabeçote sozinha.
Salvamento automático:ao reabrir a página, a última máquina volta como você deixou.

Atalhos de teclado

Espaço play/pausa
→ próximo passo
← passo anterior
↑ ↓ zoom
R reiniciar fita
F enquadrar
Ctrl+Z / Y desfazer/refazer
Ctrl+S / E / P JSON / LaTeX / PNG
Exportações: o branco é sempre B. o PNG sai sempre com fundo branco e a máquina inteira enquadrada. O botão LaTeX também baixa um .tex completo e compilável (classe standalone). O TikZ agrupa as regras de um mesmo par de estados numa única seta e desenha laços com loop above.
🎓

8. Sugestões de Atividades

  1. Use o Play e o botão ◀ para executar o exemplo aⁿbⁿ passo a passo com aabb e anote, a cada rodada, como a fita fica (XaYb, depois XXYY).
  2. Teste abbb e aabbb. Em que estado e com qual símbolo a máquina trava?
  3. Construa do zero uma MT que aceite aⁿbⁿcⁿ, linguagem que nenhum AP reconhece.
  4. Altere o exemplo da soma unária para calcular o dobro de um número unário.
  5. No exemplo MTN, descreva por que não existe ramo que aceite a entrada bbb.
  6. Exporte o diagrama em LaTeX e compile-o no seu relatório.