Riepilogo Tecnico: Una Libreria PyTorch di Reti Neurali Turing-Complete

Enunciato del Problema

Sebbene la letteratura teorica abbia da tempo stabilito che le reti neurali possono simulare le macchine di Turing (TM) — in particolare attraverso le reti ricorrenti (Siegelmann & Sontag, 1995) e i transformer con attenzione rigida (Pérez et al., 2021; Wei, Chen, & Ma, 2021) — persiste un divario significativo tra le dimostrazioni matematiche che specificano le matrici dei pesi e le implementazioni concrete ed eseguibili. Le dimostrazioni esistenti spesso si basano su precisione infinita o costruzioni astratte difficili da istanziare nei framework standard di deep learning. Questo lavoro affronta la necessità di un "riferimento concreto ed eseguibile" che colmi il divario tra i domini simbolico e neurale compilando direttamente una descrizione di macchina di Turing in una rete neurale con pesi fissi e interpretabili, senza richiedere addestramento.

Metodologia

Gli autori presentano un pacchetto PyTorch che costruisce reti neurali a partire da una data funzione di transizione della TM ($\delta$) e un insieme di stati terminali. La compilazione procede attraverso una gerarchia di componenti, garantendo che l'forward pass della rete implementi esattamente un passo della macchina specificata. Vengono implementate due architetture distinte, ciascuna realizzante un diverso risultato teorico:

1. Componenti Fondamentali

La costruzione si basa sull'assemblaggio di logica complessa a partire da porte logiche di base attivate da ReLU:

• Logica Booleana: Il lavoro dimostra come le reti ReLU implementino porte elementari (AND, OR, NOT, XOR) e le componga in circuiti a Forma Normale Disgiuntiva (DNF).
• Funzione di Transizione: La tabella di ricerca finita $\delta$ è realizzata come un circuito DNF a due livelli, dove esiste un neurone nascosto per ogni coppia stato-simbolo.
• Aritmetica Binaria: Gli additori a propagazione di riporto (ripple-carry), costruiti a partire da additori semi e additori completi, sono utilizzati per aggiornare la posizione della testina (incrementando o decrementando interi codificati in binario).
• Ricerca Posizionale: I meccanismi di attenzione rigida (approssimati tramite softmax ad alta temperatura) eseguono ricerche posizionali esatte sulla cronologia del nastro e sull'input originale, confrontando vettori chiave-query binari.

2. Architettura A: WCM21 (Basata su Transformer)

Basata sulla costruzione di Wei, Chen e Ma (2021), questa è un transformer encoder-decoder:

• Encoder: Memorizza il nastro iniziale come una matrice fissa con codifiche one-hot dei simboli e indici posizionali binari.
• Decoder: Traccia in modo autoregressivo la cronologia del calcolo. Ogni passo coinvolge una pipeline di:
  1. Transizione: Un livello feedforward che implementa la funzione di transizione della TM tramite DNF.
  2. Aritmetica: Una catena di additori a propagazione di riporto aggiorna la posizione della testina.
  3. Recupero della Cronologia: I livelli di self-attention eseguono una ricerca binaria sulla cronologia del decoder per trovare l'ultima scrittura alla posizione corrente della testina.
  4. Recupero del Nastro: La cross-attention legge il simbolo originale del nastro dall'encoder.
  5. Assemblaggio del Simbolo: Un livello feedforward basato sulla priorità seleziona il simbolo corretto (ultima scrittura > nastro originale > vuoto).
• Precisione: Utilizza codifica posizionale binaria per evitare pareggi frazionari nei punteggi di attenzione, consentendo l'implementazione con precisione finita (float32).

3. Architettura B: SS95 (Basata su Ricorrenza)

Basata su Siegelmann e Sontag (1995), questo approccio riformula la TM come una macchina a stack:

• Codifica: Gli stack sono codificati come singoli numeri razionali all'interno di un insieme di Cantor (utilizzando base $b=4$ e parametro $\rho=1/2$).
• Operazioni: Le operazioni sullo stack (push, pop, peek) sono realizzate come funzioni lineari o lineari a tratti del valore codificato, manipolate tramite moltiplicazioni di matrici e attivazioni lineari sature ($\sigma(x) = \text{clamp}(x, 0, 1)$).
• Implementazione: Vengono fornite due versioni:
  • Una versione esplicita a pipeline di 4 livelli.
  • Una versione ricorrente "in tempo reale" a 1 livello.
• Precisione: La variante a 1 livello è sensibile agli errori di arrotondamento (amplificati dalla base $b$), richiedendo float64 e limitando il numero di operazioni affidabili rispetto alla variante a 4 livelli.

Contributi Chiave

1. Esposizione Costruttiva: Una derivazione sistematica di come le reti ReLU realizzino circuiti booleani, procedendo dalle singole porte alle formule DNF e agli additori binari.
2. Implementazione Esegubile: Un pacchetto PyTorch completo che prende una descrizione TM e restituisce un modello con pesi specificati direttamente dalla definizione della macchina. Non è richiesto addestramento; la rete è "corretta per costruzione".
3. Fondamento Open-Source: Il codice funge da baseline per studiare la stabilità delle soluzioni costruite sotto perturbazione e affinamento basato su gradienti, colmando il divario tra esistenza teorica e ottimizzazione pratica.

Risultati e Capacità

Il pacchetto simula con successo macchine di Turing, dimostrato tramite un controllore di parentesi bilanciate.

• WCM21: Per una macchina con 6 stati, 5 simboli e 100 passi, il modello ha una larghezza di embedding di 59. Opera con esattezza numerica in float32, poiché tutti i valori intermedi rimangono in $\{0, 1\}$.
• SS95: La versione a 4 livelli è stabile per input tipici. La versione a 1 livello, sebbene più vicina alla costruzione teorica originale, mostra un degrado della precisione dopo circa 8 operazioni di pop a causa dell'accumulo di errori di arrotondamento nella codifica di Cantor.

Significato e Affermazioni

Il lavoro si posiziona non come una proposta di nuove applicazioni o come affermazione di prestazioni superiori rispetto ai modelli addestrati, ma come uno strumento fondamentale per l'interpretabilità e la verifica teorica.

• Interpretabilità per Costruzione: A differenza delle reti addestrate tramite discesa del gradiente, dove i neuroni possono essere permutati o intrecciati, ogni peso in queste reti costruite ha uno scopo noto e interpretabile (ad esempio, una porta specifica, un bit specifico dell'additore).
• Colmare il Divario tra Teoria e Pratica: Il lavoro chiude il divario tra dimostrazioni astratte di completezza turingiana e codice eseguibile, fornendo un riferimento concreto per il "ponte simbolico-neurale".
• Utilità Futura: Gli autori suggeriscono che i modelli servano come inizializzazioni per studiare il paesaggio della perdita attorno alle soluzioni costruite, investigando specificamente quanto la perturbazione dei pesi la simulazione possa tollerare e se l'affinamento produca scorciatoie sfuggite alla costruzione generale.

Il lavoro conclude che, sebbene queste costruzioni siano teoricamente solide e praticamente eseguibili, evidenziano i compromessi intrinseci tra la completezza turingiana teorica e la stabilità numerica pratica, in particolare nel contesto dell'aritmetica a precisione finita.