🤖 machine learning

A PyTorch Library of Turing-Complete Neural Networks

This paper introduces a PyTorch library that compiles Turing machine descriptions into exact, training-free neural network simulations using two distinct architectures: a transformer based on Wei et al. (2021) and a recurrent network based on Siegelmann and Sontag (1995).

Original authors: Jonathan Bates

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonathan Bates

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a recipe for a very specific, complex dance. Usually, to teach a robot to do this dance, you'd show it the moves thousands of times and let it "learn" through trial and error. But what if you could just hand the robot a blueprint that says, "If you see step A, do move B; if you see step C, do move D," and the robot could perform the dance perfectly on the very first try, without ever practicing?

That is exactly what this paper does, but instead of a dance, it's teaching a neural network (a type of AI) to act like a Turing Machine—the theoretical "brain" behind all modern computers.

Here is the breakdown of how they did it, using simple analogies:

1. The Big Idea: "Compile, Don't Train"

Most AI today is like a student who studies for a test by reading a textbook over and over. This paper introduces a package (a set of tools for programmers) that acts more like a translator. You give it the "rules" of a computer program (the Turing Machine), and it instantly writes the "weights" (the internal settings) of a neural network so that the network knows the rules perfectly from the start. No studying, no guessing, no training required. It is "correct by construction."

2. The Toolkit: Building Logic from Scratch

To build this translator, the authors had to show how a neural network can do basic math and logic, just like a calculator.

The Bricks (Logic Gates): They showed how to build simple "switches" (like AND, OR, NOT) inside the network. Think of these as tiny light switches that turn on or off based on specific conditions.
The Blueprint (DNF): They organized these switches into a specific pattern (like a flowchart) that can describe any rule the computer needs to follow.
The Calculator (Adders): They built a digital adder inside the network. This allows the AI to count up or down, which is essential for a computer to know where it is on its "tape" (memory).

3. Two Different Ways to Build the Machine

The paper provides two different "blueprints" (architectures) to turn these rules into a working AI.

Blueprint A: The Transformer (The "Super-Reader")

This version is based on a modern AI architecture called a Transformer (the same kind used in chatbots).

How it works: Imagine a librarian who has a massive book of history. Every time the computer needs to make a move, the librarian looks back at everything that happened before to find the right clue.
The Trick: It uses a special "hard attention" mechanism. Instead of vaguely guessing which past event is important, it acts like a laser pointer, locking onto exactly one specific piece of information from the past to make its decision.
The Result: It simulates the computer step-by-step, remembering the history of the tape and the current state perfectly.

Blueprint B: The Recurrent Network (The "Stack of Plates")

This version is based on older research from the 1990s.

How it works: Instead of a long tape, this machine thinks of memory as a stack of plates (like a spring-loaded tray in a cafeteria).
The Magic Math: The authors use a clever mathematical trick called a Cantor Set. Imagine squeezing an infinite stack of plates into a single number between 0 and 1.
- Adding a plate (pushing) is like multiplying that number.
- Removing a plate (popping) is like dividing it.
The Catch: Because this relies on squeezing infinite information into a single number, it is very sensitive to rounding errors. It works perfectly in theory, but in a real computer, if you push too many plates, the number gets too messy to read accurately.

4. Why This Matters (According to the Paper)

The authors aren't claiming this will make your phone faster or cure diseases. Instead, they are offering a proof of concept and a toolkit:

A Bridge: It connects the world of pure math (logic and Turing machines) with the world of neural networks.
A Reference: It gives researchers a perfect, runnable example to study.
Stability Check: Because the network is built perfectly by hand, scientists can now test what happens if you slightly "nudge" the settings (like adding noise or trying to fine-tune it). Does the perfect machine break, or does it stay stable?

Summary

Think of this paper as a factory manual. It doesn't just say "AI can do math." It says, "Here is the exact assembly line instructions to build a machine that does math perfectly, using only the raw materials of neural networks." It proves that if you know the rules, you can build the machine instantly, without needing to teach it how to learn.

Technical Summary: A PyTorch Library of Turing-Complete Neural Networks

Problem Statement

While theoretical literature has long established that neural networks can simulate Turing machines (TMs)—notably through recurrent networks (Siegelmann & Sontag, 1995) and transformers with hard attention (Pérez et al., 2021; Wei, Chen, & Ma, 2021)—a significant gap remains between mathematical proofs specifying weight matrices and runnable, concrete implementations. Existing proofs often rely on infinite precision or abstract constructions that are difficult to instantiate in standard deep learning frameworks. This paper addresses the need for a "concrete, runnable reference" that bridges the symbolic and neural domains by compiling a Turing machine description directly into a neural network with fixed, interpretable weights, requiring no training.

Methodology

The authors present a PyTorch package that constructs neural networks from a given TM transition function ( $\delta$ ) and set of terminal states. The compilation proceeds through a hierarchy of components, ensuring that the network's forward pass exactly implements one step of the specified machine. Two distinct architectures are implemented, each realizing a different theoretical result:

1. Core Components

The construction relies on building complex logic from basic ReLU-activated gates:

Boolean Logic: The paper demonstrates how ReLU networks implement elementary gates (AND, OR, NOT, XOR) and composes them into Disjunctive Normal Form (DNF) circuits.
Transition Function: The finite lookup table $\delta$ is realized as a two-layer DNF circuit, where one hidden neuron exists for every state-symbol pair.
Binary Arithmetic: Ripple-carry adders, constructed from half-adders and full-adders, are used to update the head position (incrementing or decrementing binary-encoded integers).
Positional Lookup: Hard-attention mechanisms (approximated via high-temperature softmax) perform exact positional lookups on the tape history and original input by matching binary key-query vectors.

2. Architecture A: WCM21 (Transformer-based)

Based on the construction by Wei, Chen, and Ma (2021), this is an encoder-decoder transformer:

Encoder: Stores the initial tape as a fixed matrix with one-hot symbol encodings and binary position indices.
Decoder: Autoregressively tracks the computation history. Each step involves a pipeline of:
1. Transition: A feedforward layer implementing the TM transition function via DNF.
2. Arithmetic: A ripple-carry adder chain updates the head position.
3. History Retrieval: Self-attention layers perform binary search over the decoder history to find the most recent write to the current head position.
4. Tape Retrieval: Cross-attention reads the original tape symbol from the encoder.
5. Symbol Assembly: A priority-based feedforward layer selects the correct symbol (last write > original tape > empty).
Precision: Uses binary positional encoding to avoid fractional ties in attention scores, allowing implementation with finite precision (float32).

3. Architecture B: SS95 (Recurrent-based)

Based on Siegelmann and Sontag (1995), this approach reformulates the TM as a stack machine:

Encoding: Stacks are encoded as single rational numbers within a Cantor set (using base $b=4$ and parameter $\rho=1/2$ ).
Operations: Stack operations (push, pop, peek) are realized as linear or piecewise-linear functions of the encoded value, manipulated via matrix multiplications and saturated linear activations ( $\sigma(x) = \text{clamp}(x, 0, 1)$ ).
Implementation: Two versions are provided:
- A 4-layer explicit pipeline version.
- A 1-layer "real-time" recurrent version.
Precision: The 1-layer variant is sensitive to rounding errors (amplified by the base $b$ ), requiring float64 and limiting the number of reliable operations compared to the 4-layer variant.

Key Contributions

Constructive Exposition: A systematic derivation of how ReLU networks realize Boolean circuits, progressing from individual gates to DNF formulas and binary adders.
Runnable Implementation: A complete PyTorch package that takes a TM description and outputs a model with weights specified directly from the machine definition. No training is required; the network is "correct by construction."
Open-Source Foundation: The codebase serves as a baseline for studying the stability of constructed solutions under perturbation and gradient-based fine-tuning, addressing the gap between theoretical existence and practical optimization.

Results and Capabilities

The package successfully simulates Turing machines, demonstrated via a balanced parentheses checker.

WCM21: For a machine with 6 states, 5 symbols, and 100 steps, the model has an embedding width of 59. It operates with numerical exactness in float32, as all intermediate values remain in $\{0, 1\}$ .
SS95: The 4-layer version is stable for typical inputs. The 1-layer version, while closer to the original theoretical construction, exhibits precision degradation after approximately 8 pop operations due to rounding error accumulation in the Cantor encoding.

Significance and Claims

The paper positions itself not as a proposal for new applications or a claim of superior performance over trained models, but as a foundational tool for interpretability and theoretical verification.

Interpretability by Construction: Unlike networks trained via gradient descent, where neurons may be permuted or entangled, every weight in these constructed networks has a known, interpretable purpose (e.g., a specific gate, a specific bit of the adder).
Bridging Theory and Practice: The work closes the gap between abstract proofs of Turing completeness and executable code, providing a concrete reference for the "symbolic–neural bridge."
Future Utility: The authors suggest the models serve as initializations for studying the loss landscape around constructed solutions, specifically investigating how much weight perturbation the simulation can tolerate and whether fine-tuning yields shortcuts missed by the general construction.

The paper concludes that while these constructions are theoretically sound and practically runnable, they highlight the inherent trade-offs between theoretical Turing completeness and practical numerical stability, particularly in the context of finite-precision arithmetic.