Resumo Técnico: Uma Biblioteca PyTorch de Redes Neurais Turing-Completas

Declaração do Problema

Embora a literatura teórica tenha estabelecido há muito tempo que redes neurais podem simular máquinas de Turing (MTs) — notadamente por meio de redes recorrentes (Siegelmann & Sontag, 1995) e transformers com atenção rígida (Pérez et al., 2021; Wei, Chen, & Ma, 2021) —, permanece uma lacuna significativa entre as provas matemáticas que especificam matrizes de pesos e implementações concretas e executáveis. As provas existentes frequentemente dependem de precisão infinita ou construções abstratas que são difíceis de instanciar em frameworks padrão de aprendizado profundo. Este artigo aborda a necessidade de uma "referência concreta e executável" que una os domínios simbólico e neural, compilando uma descrição de máquina de Turing diretamente em uma rede neural com pesos fixos e interpretáveis, sem exigir treinamento.

Metodologia

Os autores apresentam um pacote PyTorch que constrói redes neurais a partir de uma função de transição de MT ($\delta$) e um conjunto de estados terminais dados. A compilação procede através de uma hierarquia de componentes, garantindo que a passagem forward da rede implemente exatamente um passo da máquina especificada. Duas arquiteturas distintas são implementadas, cada uma realizando um resultado teórico diferente:

1. Componentes Principais

A construção depende da montagem de lógica complexa a partir de portas básicas ativadas por ReLU:

• Lógica Booleana: O artigo demonstra como redes ReLU implementam portas elementares (E, OU, NÃO, XOR) e as compõe em circuitos na Forma Normal Disjuntiva (FND).
• Função de Transição: A tabela de consulta finita $\delta$ é realizada como um circuito FND de duas camadas, onde existe um neurônio oculto para cada par estado-símbolo.
• Aritmética Binária: Somadores de propagação de carry, construídos a partir de meio-somadores e somadores completos, são usados para atualizar a posição da cabeça (incrementando ou decrementando inteiros codificados em binário).
• Consulta Posicional: Mecanismos de atenção rígida (aproximados via softmax de alta temperatura) realizam consultas posicionais exatas no histórico da fita e na entrada original, combinando vetores binários chave-pesquisa.

2. Arquitetura A: WCM21 (Baseada em Transformer)

Baseada na construção de Wei, Chen e Ma (2021), esta é uma arquitetura transformer codificador-decodificador:

• Codificador: Armazena a fita inicial como uma matriz fixa com codificações one-hot de símbolos e índices de posição binários.
• Decodificador: Rastreia autoregressivamente o histórico de computação. Cada passo envolve um pipeline de:
  1. Transição: Uma camada feedforward que implementa a função de transição da MT via FND.
  2. Aritmética: Uma cadeia de somadores de propagação de carry atualiza a posição da cabeça.
  3. Recuperação de Histórico: Camadas de auto-atenção realizam uma busca binária sobre o histórico do decodificador para encontrar a escrita mais recente na posição atual da cabeça.
  4. Recuperação da Fita: Atenção cruzada lê o símbolo original da fita a partir do codificador.
  5. Montagem de Símbolos: Uma camada feedforward baseada em prioridade seleciona o símbolo correto (última escrita > fita original > vazio).
• Precisão: Utiliza codificação posicional binária para evitar empates fracionários nas pontuações de atenção, permitindo a implementação com precisão finita (float32).

3. Arquitetura B: SS95 (Baseada em Recorrência)

Baseada em Siegelmann e Sontag (1995), esta abordagem reformula a MT como uma máquina de pilha:

• Codificação: Pilhas são codificadas como números racionais únicos dentro de um conjunto de Cantor (usando base $b=4$ e parâmetro $\rho=1/2$).
• Operações: Operações de pilha (push, pop, peek) são realizadas como funções lineares ou lineares por partes do valor codificado, manipuladas via multiplicações de matrizes e ativações lineares saturadas ($\sigma(x) = \text{clamp}(x, 0, 1)$).
• Implementação: Duas versões são fornecidas:
  • Uma versão de pipeline explícito de 4 camadas.
  • Uma versão recorrente "tempo real" de 1 camada.
• Precisão: A variante de 1 camada é sensível a erros de arredondamento (amplificados pela base $b$), exigindo float64 e limitando o número de operações confiáveis em comparação com a variante de 4 camadas.

Contribuições Principais

1. Exposição Construtiva: Uma derivação sistemática de como redes ReLU realizam circuitos booleanos, progredindo de portas individuais para fórmulas FND e somadores binários.
2. Implementação Executável: Um pacote PyTorch completo que recebe uma descrição de MT e produz um modelo com pesos especificados diretamente a partir da definição da máquina. Nenhum treinamento é necessário; a rede é "correta por construção".
3. Fundação de Código Aberto: A base de código serve como linha de base para estudar a estabilidade de soluções construídas sob perturbação e ajuste fino baseado em gradiente, abordando a lacuna entre existência teórica e otimização prática.

Resultados e Capacidades

O pacote simula com sucesso máquinas de Turing, demonstrado por meio de um verificador de parênteses balanceados.

• WCM21: Para uma máquina com 6 estados, 5 símbolos e 100 passos, o modelo possui uma largura de incorporação de 59. Opera com exatidão numérica em float32, pois todos os valores intermediários permanecem em $\{0, 1\}$.
• SS95: A versão de 4 camadas é estável para entradas típicas. A versão de 1 camada, embora mais próxima da construção teórica original, exibe degradação de precisão após aproximadamente 8 operações de pop devido ao acúmulo de erros de arredondamento na codificação de Cantor.

Significado e Alegações

O artigo posiciona-se não como uma proposta de novas aplicações ou uma alegação de desempenho superior sobre modelos treinados, mas como uma ferramenta fundamental para interpretabilidade e verificação teórica.

• Interpretabilidade por Construção: Diferentemente de redes treinadas via descida de gradiente, onde neurônios podem ser permutados ou emaranhados, cada peso nessas redes construídas tem um propósito conhecido e interpretável (por exemplo, uma porta específica, um bit específico do somador).
• Unindo Teoria e Prática: O trabalho fecha a lacuna entre provas abstratas de completude de Turing e código executável, fornecendo uma referência concreta para a "ponte simbólica–neural".
• Utilidade Futura: Os autores sugerem que os modelos sirvam como inicializações para estudar a paisagem de perda ao redor de soluções construídas, investigando especificamente quanto a perturbação de pesos a simulação pode tolerar e se o ajuste fino produz atalhos ignorados pela construção geral.

O artigo conclui que, embora essas construções sejam teoricamente sólidas e praticamente executáveis, elas destacam as compensações inerentes entre a completude de Turing teórica e a estabilidade numérica prática, particularmente no contexto da aritmética de precisão finita.