Resumen Técnico: Una Biblioteca PyTorch de Redes Neuronales Turing-Completas

Enunciado del Problema

Aunque la literatura teórica ha establecido desde hace tiempo que las redes neuronales pueden simular máquinas de Turing (MT)—notablemente a través de redes recurrentes (Siegelmann & Sontag, 1995) y transformadores con atención dura (Pérez et al., 2021; Wei, Chen, & Ma, 2021)—persiste una brecha significativa entre las pruebas matemáticas que especifican matrices de pesos y las implementaciones concretas y ejecutables. Las pruebas existentes a menudo dependen de precisión infinita o construcciones abstractas que son difíciles de instanciar en marcos de aprendizaje profundo estándar. Este artículo aborda la necesidad de una "referencia concreta y ejecutable" que conecte los dominios simbólico y neuronal compilando una descripción de máquina de Turing directamente en una red neuronal con pesos fijos e interpretables, sin requerir entrenamiento.

Metodología

Los autores presentan un paquete de PyTorch que construye redes neuronales a partir de una función de transición de MT ($\delta$) dada y un conjunto de estados terminales. La compilación procede a través de una jerarquía de componentes, asegurando que el paso forward de la red implemente exactamente un paso de la máquina especificada. Se implementan dos arquitecturas distintas, cada una realizando un resultado teórico diferente:

1. Componentes Principales

La construcción se basa en crear lógica compleja a partir de puertas básicas activadas por ReLU:

• Lógica Booleana: El artículo demuestra cómo las redes ReLU implementan puertas elementales (AND, OR, NOT, XOR) y las compone en circuitos de Forma Normal Disyuntiva (DNF).
• Función de Transición: La tabla de búsqueda finita $\delta$ se realiza como un circuito DNF de dos capas, donde existe una neurona oculta por cada par estado-símbolo.
• Aritmética Binaria: Sumadores de propagación de acarreo, construidos a partir de semisumadores y sumadores completos, se utilizan para actualizar la posición de la cabeza (incrementando o decrementando enteros codificados en binario).
• Búsqueda Posicional: Los mecanismos de atención dura (aproximados mediante softmax de alta temperatura) realizan búsquedas posicionales exactas en el historial de la cinta y en la entrada original, emparejando vectores binarios clave-cuestión.

2. Arquitectura A: WCM21 (Basada en Transformadores)

Basada en la construcción de Wei, Chen y Ma (2021), esta es una arquitectura transformadora codificador-decodificador:

• Codificador: Almacena la cinta inicial como una matriz fija con codificaciones one-hot de símbolos e índices de posición binarios.
• Decodificador: Rastrea autoregresivamente el historial de cómputo. Cada paso implica una tubería de:
  1. Transición: Una capa de alimentación directa que implementa la función de transición de la MT mediante DNF.
  2. Aritmética: Una cadena de sumadores de propagación de acarreo actualiza la posición de la cabeza.
  3. Recuperación del Historial: Las capas de autoatención realizan una búsqueda binaria sobre el historial del decodificador para encontrar la escritura más reciente en la posición actual de la cabeza.
  4. Recuperación de la Cinta: La atención cruzada lee el símbolo original de la cinta desde el codificador.
  5. Ensamblaje de Símbolos: Una capa de alimentación directa basada en prioridades selecciona el símbolo correcto (última escritura > cinta original > vacío).
• Precisión: Utiliza codificación posicional binaria para evitar empates fraccionarios en las puntuaciones de atención, permitiendo la implementación con precisión finita (float32).

3. Arquitectura B: SS95 (Basada en Recurrencia)

Basada en Siegelmann y Sontag (1995), este enfoque reformula la MT como una máquina de pila:

• Codificación: Las pilas se codifican como números racionales individuales dentro de un conjunto de Cantor (usando base $b=4$ y parámetro $\rho=1/2$).
• Operaciones: Las operaciones de pila (push, pop, peek) se realizan como funciones lineales o lineales por partes del valor codificado, manipuladas mediante multiplicaciones de matrices y activaciones lineales saturadas ($\sigma(x) = \text{clamp}(x, 0, 1)$).
• Implementación: Se proporcionan dos versiones:
  • Una versión explícita de tubería de 4 capas.
  • Una versión recurrente de "tiempo real" de 1 capa.
• Precisión: La variante de 1 capa es sensible a errores de redondeo (amplificados por la base $b$), requiriendo float64 y limitando el número de operaciones fiables en comparación con la variante de 4 capas.

Contribuciones Clave

1. Exposición Constructiva: Una derivación sistemática de cómo las redes ReLU realizan circuitos booleanos, progresando desde puertas individuales hasta fórmulas DNF y sumadores binarios.
2. Implementación Ejecutable: Un paquete completo de PyTorch que toma una descripción de MT y genera un modelo con pesos especificados directamente desde la definición de la máquina. No se requiere entrenamiento; la red es "correcta por construcción".
3. Fundamento de Código Abierto: La base de código sirve como línea base para estudiar la estabilidad de las soluciones construidas bajo perturbación y ajuste fino basado en gradientes, abordando la brecha entre la existencia teórica y la optimización práctica.

Resultados y Capacidades

El paquete simula exitosamente máquinas de Turing, demostrado mediante un verificador de paréntesis balanceados.

• WCM21: Para una máquina con 6 estados, 5 símbolos y 100 pasos, el modelo tiene un ancho de incrustación de 59. Opera con exactitud numérica en float32, ya que todos los valores intermedios permanecen en $\{0, 1\}$.
• SS95: La versión de 4 capas es estable para entradas típicas. La versión de 1 capa, aunque más cercana a la construcción teórica original, muestra degradación de precisión después de aproximadamente 8 operaciones pop debido a la acumulación de errores de redondeo en la codificación de Cantor.

Significado y Afirmaciones

El artículo se posiciona no como una propuesta de nuevas aplicaciones ni como una afirmación de rendimiento superior sobre modelos entrenados, sino como una herramienta fundamental para la interpretabilidad y la verificación teórica.

• Interpretabilidad por Construcción: A diferencia de las redes entrenadas mediante descenso de gradiente, donde las neuronas pueden estar permutadas o entrelazadas, cada peso en estas redes construidas tiene un propósito conocido e interpretable (por ejemplo, una puerta específica, un bit específico del sumador).
• Conectando Teoría y Práctica: El trabajo cierra la brecha entre pruebas abstractas de completitud de Turing y código ejecutable, proporcionando una referencia concreta para el "puente simbólico-neuronal".
• Utilidad Futura: Los autores sugieren que los modelos sirven como inicializaciones para estudiar el paisaje de pérdida alrededor de las soluciones construidas, investigando específicamente cuánto puede tolerar la simulación la perturbación de pesos y si el ajuste fino produce atajos omitidos por la construcción general.

El artículo concluye que, aunque estas construcciones son teóricamente sólidas y prácticamente ejecutables, destacan las compensaciones inherentes entre la completitud de Turing teórica y la estabilidad numérica práctica, particularmente en el contexto de la aritmética de precisión finita.