Máquina de Turing

Uma fita infinita e uma cabeça que lê, escreve e se move

Imagine uma fita dividida em células, cada uma contendo um símbolo. Uma cabeça de leitura/escrita aponta para uma célula e, baseando-se no estado atual e no símbolo que lê, decide: qual símbolo escrever, para qual lado mover a cabeça e para qual estado ir.

Esse modelo absurdamente simples — descrito em 1936, antes de existir qualquer computador eletrônico — captura toda a computação possível. Qualquer algoritmo que você escreve em Python pode ser traduzido para uma Máquina de Turing equivalente, e vice-versa.

TM de incremento binário

A máquina percorre a fita até o fim, depois volta incrementando da direita: 1→0 com carry, para em 0→1. Tente "0111" (→"1000") ou "111" (overflow → "1000").

Simulando uma Máquina de Turing

# Máquina de Turing — definição formal e simulação
# TM = (Q, Σ, Γ, δ, q₀, B, F)
#   Q: estados finitos
#   Σ: alfabeto de entrada
#   Γ: alfabeto da fita (Σ ⊆ Γ, inclui B = branco)
#   δ: Q × Γ → Q × Γ × {L, R} (transição)
#   q₀: estado inicial
#   B: símbolo branco
#   F: estados de aceitação

# TM para incremento binário: "0111" → "1000"
delta = {
    # (estado_atual, símbolo_lido): (próx_estado, símbolo_escrito, direção)
    ("q0", "0"): ("q0", "0", "R"),   # q0: varre direita
    ("q0", "1"): ("q0", "1", "R"),
    ("q0", "B"): ("q1", "B", "L"),   # chegou ao fim → vai esquerda
    ("q1", "1"): ("q1", "0", "L"),   # q1: flip 1→0, carry
    ("q1", "0"): ("qf", "1", "R"),   # absorve carry
    ("q1", "B"): ("qf", "1", "R"),   # overflow: todos eram 1
}

def run_tm(tape_input):
    tape  = list("B" + tape_input + "BBB")
    head  = 1
    state = "q0"
    while state != "qf":
        sym  = tape[head] if head < len(tape) else "B"
        next_state, write, move = delta[(state, sym)]
        tape[head] = write
        head += 1 if move == "R" else -1
        state = next_state
    return "".join(tape).strip("B")

Tese de Church-Turing e o Problema da Parada

# Tese de Church-Turing e Decidibilidade

# Tese de Church-Turing (1936):
# "Todo processo que intuitivamente consideramos computável
#  pode ser computado por uma Máquina de Turing."
# → Python, C, Rust, JavaScript são Turing-completos.
#   Qualquer um pode simular qualquer outro.

# Problemas DECIDÍVEIS (TM sempre para e aceita ou rejeita):
# - Testar se uma string está em uma linguagem regular
# - Testar se um número é primo
# - Ordenar uma lista

# Problema da PARADA (Halting Problem) — INDECIDÍVEL:
# "Dado um programa P e uma entrada I,
#  P termina em I?" → nenhuma TM decide isso

# Prova (Turing, 1936) — por contradição:
# Suponha que HALT(P, I) existe e decide o problema
def paradoxo(P):
    if HALT(P, P):   # se P para quando roda sobre si mesmo...
        loop()       # ...então loop
    else:            # se P não para...
        return       # ...então para

# paradoxo(paradoxo): contradição em ambos os casos → HALT não existe
# Implicação prática: não existe ferramenta que analise
# arbitrariamente código e decida se ele termina.

Construindo simuladores de TM

Mini projeto: implemente um simulador genérico de Máquina de Turing em Python. Represente a tabela de transições como um dicionário e a fita como um defaultdict(lambda: "B"). Execute a TM do incremento binário e verifique os resultados para "0", "1", "1111", "10101".

Projeto principal: implemente uma Máquina de Turing de 2 fitas para multiplicar dois números unários (representados como sequências de 1s). Use a segunda fita como espaço de trabalho. Compare com a versão de 1 fita para entender como múltiplas fitas simplificam algoritmos (ambas têm o mesmo poder, mas a 2-fitas é polinomialmente mais eficiente).

Desafio extra: pesquise o Busy Beaver problem — qual TM de N estados escreve o maior número de 1s antes de parar? Para N=2 o máximo é 4; para N=5, 4098. Para N=6 é desconhecido. Implemente um enumerador e runner para explorar TMs de 2-3 estados e encontrar a campeã. O problema é indecidível — mas para N pequeno é enumerável.

Teste sua intuição

Onde você encontra isso