A PyTorch Library of Turing-Complete Neural Networks

# A PyTorch Library of Turing-Complete Neural Networks
Source: [https://arxiv.org/html/2605.08150](https://arxiv.org/html/2605.08150)
###### Abstract

We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training\. Given a transition function and a set of terminal states, the package constructs a model whose forward pass corresponds to one step of the Turing machine\. Two architectures are implemented, each realizing a different theoretical result: \(1\) a transformer with self\-attention, cross\-attention, and feedforward layers based on Wei, Chen, and Ma \(2021\), and \(2\) a recurrent network based on Siegelmann and Sontag \(1995\) that encodes the stack in a Cantor set\. We develop the constructions from first principles, showing how ReLU networks implement Boolean circuits \(AND, OR, NOT, XOR gates and their composition into DNF formulas and binary adders\) and how hard attention implements positional lookup on the tape\. The package serves as a concrete, runnable reference for the symbolic–neural bridge, and as a foundation for future work on the stability of constructed solutions under gradient\-based optimization\. Code is available at[https://github\.com/jonrbates/turing](https://github.com/jonrbates/turing)\.

## 1Introduction

Can a neural network simulate a Turing machine? The question has been answered affirmatively multiple times in the theoretical literature: by Siegelmann and Sontag\[[8](https://arxiv.org/html/2605.08150#bib.bib8),[9](https://arxiv.org/html/2605.08150#bib.bib9)\]using recurrent networks, by Pérez et al\.\[[7](https://arxiv.org/html/2605.08150#bib.bib7)\]using transformers with hard attention, and by Wei, Chen, and Ma\[[11](https://arxiv.org/html/2605.08150#bib.bib11)\]using a finite\-precision transformer with binary positional encoding\. More recently, Li and Wang\[[4](https://arxiv.org/html/2605.08150#bib.bib4)\]showed that even constant bit\-size transformers are Turing complete, given a sufficiently long context window and chain\-of\-thought steps\. These results give explicit constructions, but they live on paper: the gap between a proof specifying weight matrices and a runnable implementation remains\.

In this paper, we describe a PyTorch package that closes that gap\. Given a Turing machine specified by its transition function and terminal states, the package constructs a neural network and*specifies*all weights and biases so that the network’s forward pass exactly implements one step of the machine\. No training is required: the network is correct by construction\. \(For the WCM21 transformer, weights are set by direct construction from the transition table; for the SS95 recurrent network, a least\-squares solution determines the weights from the configuration space\.\)

The compilation from machine description to neural network proceeds through a hierarchy of components:

1. 1\.Logic gates\.ReLU networks compute AND, OR, NOT, and XOR on binary\-valued subsets of the state vector\.
2. 2\.Transition function\.The finite lookup tableδ\\deltais realized as a two\-layer DNF circuit: one hidden neuron per state\-symbol pair\.
3. 3\.Binary arithmetic\.Half\-adders and full adders, composed from the above gates, form a ripple\-carry adder that updates the head position\.
4. 4\.Positional lookup\.Hard\-attention layers with binary key\-query matching retrieve symbols from the tape history and the original input\.
5. 5\.Symbol assembly\.Feedforward layers select the correct symbol at the new head position by priority: last write, original tape, or empty\.

Every weight in the resulting network has a known, interpretable purpose\. This interpretability is a property of the*construction process*, not of post\-hoc analysis, a point we return to in the discussion\.

Two simulation architectures are provided:

- •WCM21\(Wei, Chen & Ma, 2021\): an encoder\-decoder transformer in which the encoder stores the initial tape and the decoder autoregressively tracks the computation history\. Self\-attention retrieves past writes; cross\-attention reads the original tape; feedforward layers implement the transition function and binary arithmetic\.
- •SS95\(Siegelmann & Sontag, 1992; 1995\): a recurrent network that reformulates the Turing machine as a stack machine and encodes each stack as a single rational number using a Cantor\-set encoding\. Two versions are implemented: a 4\-layer network with explicit pipeline stages, and a 1\-layer “real\-time” variant\.

#### Contributions\.

1. 1\.A self\-contained exposition of how ReLU networks realize Boolean circuits, building from individual gates through DNF to binary adders\.
2. 2\.A constructive implementation of two Turing machine simulation results as a PyTorch package with weights specified from the machine description\.
3. 3\.An open\-source codebase suitable for studying the stability of constructed solutions under perturbation and gradient\-based fine\-tuning\.

#### Related work\.

Pérez et al\.\[[7](https://arxiv.org/html/2605.08150#bib.bib7)\]gave an explicit construction of a transformer with hard attention that simulates any Turing machine, using a single\-layer encoder and three\-layer decoder\. Their construction operates over rationals of arbitrary precision; when multiple positions tie for the maximum attention score, the hardmax produces fractions like1/t1/t, requiring precision to grow with the sequence length\.

Wei, Chen, and Ma\[[11](https://arxiv.org/html/2605.08150#bib.bib11)\]avoid this by using*binary positional encoding*\. Head positions and step numbers are represented as fixed\-width binary vectors, and position lookup is performed by matching binary bits via attention scores that never produce fractional ties\. This is the key modification that makes the construction implementable at finite precision\. The number of parameters is polynomial in the alphabet size\|Γ\|\|\\Gamma\|, state space size\|Q\|\|Q\|, andlog⁡T\\log T, rather than growing with the input length\. The WCM21 implementation follows the Wei\-Chen\-Ma construction directly, translating Claims C\.4–C\.6 and Lemmas C\.1, C\.2, C\.7, C\.8 into PyTorch modules; the binary encoding is realized by the ripple\-carry adder and binary search layers\.

The next line of work introduced*chain\-of\-thought \(CoT\)*as a computational resource for transformers\. Li et al\.\[[3](https://arxiv.org/html/2605.08150#bib.bib3)\]proved that constant\-depth, constant\-precision transformers augmented withO​\(log⁡t\)O\(\\log t\)chain\-of\-thought steps can solve problems requiring serial computation, and Merrill and Sabharwal\[[5](https://arxiv.org/html/2605.08150#bib.bib5)\]characterized the expressive power of such CoT\-augmented transformers, showing that polynomial CoT steps yield the power of polynomial\-time Turing machines\. These results formalize the intuition that intermediate generation steps can serve as a work tape\.

Li and Wang\[[4](https://arxiv.org/html/2605.08150#bib.bib4)\]pushed this further, proving that even constant bit\-size transformers \(fixed precision and fixed parameter count\) are Turing complete when given sufficient context window length, using Post machine simulation with chain\-of\-thought steps\.

Table 1:Resource requirements for neural Turing\-completeness constructions\.ttandssdenote the worst\-case runtime and space of the simulated machine over inputs of lengthnn\. Transformer rows adapted from Li and Wang\[[4](https://arxiv.org/html/2605.08150#bib.bib4)\], Table 1\.Smolensky et al\.\[[10](https://arxiv.org/html/2605.08150#bib.bib10)\]developed PSL \(Production System Language\), a high\-level language for symbolic programs that compiles into transformer weights using Tensor Product Representations\. PSL operates at the level of production rules over structured working memory; the constructions here expose the lower\-level circuit primitives \(gates, adders, hard attention\) that realize the computation\.

The Neural Turing Machine\[[2](https://arxiv.org/html/2605.08150#bib.bib2)\]and related differentiable memory architectures are inspired by and inductively biased to emulate computer architecture\. The approach here instead compiles any given program into fixed weights\.

## 2Preliminaries

### 2\.1Turing Machines

###### Definition 1\(Turing Machine\)\.

A Turing machine is a tupleM=\(Q,Γ,δ,q0,F\)M=\(Q,\\Gamma,\\delta,q\_\{0\},F\)whereQQis a finite set of states,Γ\\Gammais a finite tape alphabet,δ:Q×Γ→Q×Γ×\{−1,\+1\}\\delta:Q\\times\\Gamma\\to Q\\times\\Gamma\\times\\\{\-1,\+1\\\}is the \(partial\) transition function,q0∈Qq\_\{0\}\\in Qis the initial state, andF⊆QF\\subseteq Qis the set of terminal \(halting\) states\. Given a stateqqand a symbolaaunder the head,δ​\(q,a\)=\(q′,a′,d\)\\delta\(q,a\)=\(q^\{\\prime\},a^\{\\prime\},d\)specifies the next stateq′q^\{\\prime\}, the symbola′a^\{\\prime\}to write, and the directionddto move the head\.

A*configuration*at timettis the triple\(qt,ht,τt\)\(q\_\{t\},h\_\{t\},\\tau\_\{t\}\): the current stateqt∈Qq\_\{t\}\\in Q, the head positionht∈\{0,…,n−1\}h\_\{t\}\\in\\\{0,\\ldots,n\-1\\\}, and the tape contentsτt∈Γn\\tau\_\{t\}\\in\\Gamma^\{n\}\. The machine halts whenqt∈Fq\_\{t\}\\in F\.

###### Example 1\(Balanced Parentheses\)\.

Consider the language of balanced parenthesis strings\. We define a Turing machine with statesQ=\{I,R,M,V,T,F\}Q=\\\{I,R,M,V,T,F\\\}, alphabetΓ=\{B,E,\(,\),∗\}\\Gamma=\\\{B,E,\(,\),\*\\\}, initial stateq0=Iq\_\{0\}=I, and terminal states\{T,F\}\\\{T,F\\\}\(“True” and “False”\)\. The tape is initialized with sentinelsBBandEEflanking the input, e\.g\.,B\(\)\(\(\(\)\(\(\)\)\)\(\)\)E\. The transition function is given in Table[2](https://arxiv.org/html/2605.08150#S2.T2)\.

The machine scans right in stateRRuntil it finds a close parenthesis; switches to stateMMand scans left to find a matching open parenthesis \(replacing both with∗\*\); then resumes scanning right\. StateVVverifies that no unmatched symbols remain\.

Table 2:Transition functionδ\\deltafor the balanced parentheses machine\.StateReadNext StateWriteMoveIIBBRRBB\+1\+1RR\(\(RR\(\(\+1\+1RR\)\)MM∗\*−1\-1RR∗\*RR∗\*\+1\+1RREEVVEE−1\-1MMBBFF∗\*−1\-1MM\(\(RR∗\*\+1\+1MM∗\*MM∗\*−1\-1VV\(\(FF∗\*−1\-1VV∗\*VV∗\*−1\-1VVBBTTBB\+1\+1Figure 1:Execution trace on inputB\(\)E\. The head scans right in stateRR, matches parentheses in stateMM, and verifies in stateVV\. Matched pairs are replaced with\*\. Head symbolhighlighted\.
### 2\.2Notation and Activations

We writeReLU​\(x\)=max⁡\(x,0\)\\mathrm\{ReLU\}\(x\)=\\max\(x,0\)for the rectified linear unit\. When inputs are restricted to\{0,1\}\\\{0,1\\\}, the constructions in this paper are designed so that all intermediate values remain in\{0,1\}\\\{0,1\\\}underReLU\\mathrm\{ReLU\}\. The*saturated linear*activationσ​\(x\)=clamp⁡\(x,0,1\)\\sigma\(x\)=\\operatorname\{clamp\}\(x,\\,0,\\,1\), which explicitly clamps outputs to\[0,1\]\[0,1\], is used in the SS95 construction \(§[6](https://arxiv.org/html/2605.08150#S6)\) where Cantor\-set encoded values require bounded activations\.

## 3Boolean Circuits in ReLU Networks

A fundamental observation underlying the constructions is that networks with piecewise\-linear activations can exactly implement Boolean logic\. We develop this systematically\.

### 3\.1Elementary Gates

###### Proposition 2\(NOT\)\.

Forx∈\{0,1\}x\\in\\\{0,1\\\}:¬x=ReLU​\(1−x\)\\neg x=\\mathrm\{ReLU\}\(1\-x\)\.

###### Proposition 3\(AND\)\.

Forx1,x2∈\{0,1\}x\_\{1\},x\_\{2\}\\in\\\{0,1\\\}:x1∧x2=ReLU​\(x1\+x2−1\)x\_\{1\}\\wedge x\_\{2\}=\\mathrm\{ReLU\}\(x\_\{1\}\+x\_\{2\}\-1\)\. This generalizes:⋀i=1kxi=ReLU​\(∑i=1kxi−\(k−1\)\)\\bigwedge\_\{i=1\}^\{k\}x\_\{i\}=\\mathrm\{ReLU\}\\\!\\left\(\\sum\_\{i=1\}^\{k\}x\_\{i\}\-\(k\-1\)\\right\)\.

###### Proposition 4\(NOR and OR\)\.

NOR​\(x1,x2\)=ReLU​\(1−x1−x2\)\\mathrm\{NOR\}\(x\_\{1\},x\_\{2\}\)=\\mathrm\{ReLU\}\(1\-x\_\{1\}\-x\_\{2\}\)and

OR​\(x1,x2\)=NOT​\(NOR​\(x1,x2\)\)=ReLU​\(1−ReLU​\(1−x1−x2\)\)\.\\mathrm\{OR\}\(x\_\{1\},x\_\{2\}\)=\\mathrm\{NOT\}\(\\mathrm\{NOR\}\(x\_\{1\},x\_\{2\}\)\)=\\mathrm\{ReLU\}\(1\-\\mathrm\{ReLU\}\(1\-x\_\{1\}\-x\_\{2\}\)\)\.

###### Proposition 5\(XOR\)\.

x1⊕x2x\_\{1\}\\oplus x\_\{2\}is not linearly separable and cannot be computed by a single neuron\. The implementation uses:

x1⊕x2=AND​\(NAND​\(x1,x2\),OR​\(x1,x2\)\)\.x\_\{1\}\\oplus x\_\{2\}=\\mathrm\{AND\}\(\\mathrm\{NAND\}\(x\_\{1\},x\_\{2\}\),\\;\\mathrm\{OR\}\(x\_\{1\},x\_\{2\}\)\)\.\(1\)

### 3\.2Embedding Gates in Weight Matrices

A key implementation technique is that gates operating on a*subset*of dimensions can be embedded in a large weight matrix that acts as the identity on all other dimensions\. Starting fromW=IW=I, we modify the rows and columns corresponding to the gate’s inputs and outputs\. This allows multiple gates to be applied in parallel, and circuits to be composed by sequential matrix\-ReLU\\mathrm\{ReLU\}layers\.

For example, to computeAND​\(xi,xj\)\\mathrm\{AND\}\(x\_\{i\},x\_\{j\}\)and store the result at positioniiwhile passing all other dimensions through unchanged:

W=I,Wi​j=1,bi=−1,W=I,\\quad W\_\{ij\}=1,\\quad b\_\{i\}=\-1,\(2\)so that\[ReLU​\(W​x\+b\)\]i=ReLU​\(xi\+xj−1\)\[\\mathrm\{ReLU\}\(Wx\+b\)\]\_\{i\}=\\mathrm\{ReLU\}\(x\_\{i\}\+x\_\{j\}\-1\)and\[ReLU​\(W​x\+b\)\]k=xk\[\\mathrm\{ReLU\}\(Wx\+b\)\]\_\{k\}=x\_\{k\}fork≠ik\\neq i\.

### 3\.3DNF Realization and the Transition Function

Any Boolean functionf:\{0,1\}n→\{0,1\}f:\\\{0,1\\\}^\{n\}\\to\\\{0,1\\\}can be written in disjunctive normal form \(DNF\):f​\(x\)=⋁jCj​\(x\)f\(x\)=\\bigvee\_\{j\}C\_\{j\}\(x\), where each clauseCjC\_\{j\}is a conjunction of literals\.

###### Theorem 6\(DNF Realization\)\.

Any DNF withmmclauses overnnvariables can be computed by a three\-layer ReLU network: Layer 1 computes each clause via AND \(mmhidden neurons\), Layer 2 computes NOR of the clause outputs, and Layer 3 negates to produce OR\. When the clauses are mutually exclusive \(at most one is active\), Layer 2 can compute OR directly by summation, reducing the network to two layers\.

The Turing machine transition functionδ\\deltais a finite lookup table mapping\(q,a\)\(q,a\)pairs to\(q′,a′,d\)\(q^\{\\prime\},a^\{\\prime\},d\)triples\. With one\-hot encodings, each table entry is a clause: “state isqq” AND “symbol isaa”\. The first layer appends\|Q\|⋅\|Γ\|\|Q\|\\cdot\|\\Gamma\|detector dimensions \(one per state\-symbol pair\), each a 2\-input AND with bias−1\-1\. AfterReLU\\mathrm\{ReLU\}, exactly one detector fires\. The second layer routes the outputs: for each entryδ​\(q,a\)=\(q′,a′,d\)\\delta\(q,a\)=\(q^\{\\prime\},a^\{\\prime\},d\), it sets a 1 in the output column for next stateq′q^\{\\prime\}, write symbola′a^\{\\prime\}, and directiondd\. Position\-encoding bits \(pos1,pos2\) are passed through unchanged via the identity block\.

In the package, this is theTransitionmodule:W1∈ℝ\(w\+s​g\)×wW\_\{1\}\\in\\mathbb\{R\}^\{\(w\+sg\)\\times w\}andW2∈ℝw×\(w\+s​g\)W\_\{2\}\\in\\mathbb\{R\}^\{w\\times\(w\+sg\)\}\.

## 4Binary Arithmetic

To update the head position, we must add or subtract 1 from a binary\-encoded integer\. This requires binary addition circuits built from the gates of §[3](https://arxiv.org/html/2605.08150#S3)\.

### 4\.1Half Adder

A half adder takes two bitsa,b∈\{0,1\}a,b\\in\\\{0,1\\\}and produces a sums=a⊕bs=a\\oplus band a carryc=a∧bc=a\\wedge b\. The implementation uses three layers, each embedded in add\-dimensional identity matrix, operating on positionsii\(overwritten with sum\) andjj\(overwritten with carry\):

1. 1\.ComputeAND​\(xi,xj\)\\mathrm\{AND\}\(x\_\{i\},x\_\{j\}\)at positioniiandNOR​\(xi,xj\)\\mathrm\{NOR\}\(x\_\{i\},x\_\{j\}\)at positionjjsimultaneously\.
2. 2\.Negate both:NAND=NOT​\(AND​\(xi,xj\)\)\\mathrm\{NAND\}=\\mathrm\{NOT\}\(\\mathrm\{AND\}\(x\_\{i\},x\_\{j\}\)\)at positionii,OR=NOT​\(NOR​\(xi,xj\)\)\\mathrm\{OR\}=\\mathrm\{NOT\}\(\\mathrm\{NOR\}\(x\_\{i\},x\_\{j\}\)\)at positionjj\.
3. 3\.Combine:s=xi⊕xj=AND​\(NAND,OR\)s=x\_\{i\}\\oplus x\_\{j\}=\\mathrm\{AND\}\(\\mathrm\{NAND\},\\mathrm\{OR\}\)at positionii;c=NOT​\(NAND\)c=\\mathrm\{NOT\}\(\\mathrm\{NAND\}\)at positionjj\.

AND and NOR share the first layer because they have the same computational structure \(weighted sum plusReLU\\mathrm\{ReLU\}\) with opposite signs\. Listing[1](https://arxiv.org/html/2605.08150#LST1)shows the complete PyTorch implementation\. Each layer starts from thed×dd\\times didentity matrix and modifies only the rows for positionsiiandjj\. All other dimensions pass through unchanged, so the half adder can be embedded in an arbitrarily large state vector\.

1

2W1=torch\.eye\(d\_in\)

3b1=torch\.zeros\(d\_in\)

4W1\[i,j\]=1;b1\[i\]=\-1

5W1\[j,i\]=\-1;W1\[j,j\]=\-1;b1\[j\]=1

6

7

8

9W2=torch\.eye\(d\_in\)

10b2=torch\.zeros\(d\_in\)

11W2\[i,i\]=\-1;b2\[i\]=1

12W2\[j,j\]=\-1;b2\[j\]=1

13

14

15W3=torch\.eye\(d\_in\)

16b3=torch\.zeros\(d\_in\)

17W3\[i,j\]=1;b3\[i\]=\-1

18W3\[j,i\]=\-1;W3\[j,j\]=0;b3\[j\]=1

19

Listing 1:The half adder\. Three linear\-ReLU layers computesum=xi⊕xj\\mathrm\{sum\}=x\_\{i\}\\oplus x\_\{j\}at positioniiandcarry=xi∧xj\\mathrm\{carry\}=x\_\{i\}\\wedge x\_\{j\}at positionjj\.
### 4\.2Full Adder

A full adder takes three bitsaa,bb,cinc\_\{\\mathrm\{in\}\}and producess=a⊕b⊕cins=a\\oplus b\\oplus c\_\{\\mathrm\{in\}\}andcout=\(a∧b\)∨\(cin∧\(a⊕b\)\)c\_\{\\mathrm\{out\}\}=\(a\\wedge b\)\\vee\(c\_\{\\mathrm\{in\}\}\\wedge\(a\\oplus b\)\)\. It cascades two half\-adders followed by two layers that compute the OR of the intermediate carries \(via NOR then NOT\)\.

In the WCM21 simulator, a chain of⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceilfull adders forms a ripple\-carry adder\. ThePreprocessForAddermodule sets up the operands: for a right move \(d=\+1d=\+1\), the addend is the binary representation of 1 \(a single 1\-bit in the least significant position\); for a left move \(d=−1d=\-1\), the addend is all ones, implementing subtraction via two’s complement\. The direction is read fromscr5, which was set by the transition layer\.

## 5The WCM21 Construction

We now describe the full simulation architecture based on Wei, Chen, and Ma\[[11](https://arxiv.org/html/2605.08150#bib.bib11)\]\. The network is an encoder\-decoder transformer whose weights are specified from the machine description\.

### 5\.1Architecture Overview

Theencoderprocesses the initial tape once\. Each of thenntape positions is encoded as a row of a matrixE∈ℝn×wE\\in\\mathbb\{R\}^\{n\\times w\}, containing a one\-hot symbol encoding and a binary position index\.EEis fixed throughout the simulation\.

Thedecodermaintains a growing sequence of state vectorsH=\[h0,h1,…,ht−1\]H=\[h\_\{0\},h\_\{1\},\\ldots,h\_\{t\-1\}\], one per simulation step\. Each vectorht∈ℝwh\_\{t\}\\in\\mathbb\{R\}^\{w\}encodes the machine state, the symbol at the current position, the step number, the head position, and scratch space for intermediate computation\. After each step, a position embeddingβ​\(t\)\\beta\(t\)encoding the step number is added to the new vector before it is appended toHH\.

The embedding dimensionwwis partitioned into named slices:

For the balanced parentheses example \(6 states, 5 symbols,T=100T=100\), we have⌈log2⁡100⌉=7\\lceil\\log\_\{2\}100\\rceil=7, givingw=6\+2​\(5\)\+3​\(7\)\+22=59w=6\+2\(5\)\+3\(7\)\+22=59\.

### 5\.2One Simulation Step

Each step applies the following pipeline to the most recent decoder vector, producing a new vector that is appended toHH\. We reference the corresponding claims and lemmas from\[[11](https://arxiv.org/html/2605.08150#bib.bib11)\]\.

1. 1\.Transition\(feedforward, Lemma C\.1\)\. Two linear layers withReLU\\mathrm\{ReLU\}implement the transition functionδ\\deltaas a DNF circuit \(§[3\.3](https://arxiv.org/html/2605.08150#S3.SS3)\)\. Readsstandsym1; writes next state tost, written symbol tosym2, and direction toscr5\.
2. 2\.Preprocess for Adder\(linear, Lemma C\.2\)\. Copiespos2intopos3and extends the vector by⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceildimensions for the second operand, initialized from the direction inscr5\.
3. 3\.Adder Chain\(feedforward, Lemma C\.2\)\. A ripple\-carry adder of⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceilFullAddermodules computes the new head position inpos3\.
4. 4\.Project Down\(linear\)\. Drops the extra adder dimensions, returning to widthww\.
5. 5\.Indicate Visited Position\(self\-attention \+ linear, Claim C\.4\)\. A self\-attention layer overHHdetermines whether the new positionpos3has been visited in any previous step\. The query matches onpos3against thepos2of all previous steps\. A flag is stored inscr4\.
6. 6\.Binary Search\(⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceilself\-attention layers, Claim C\.5\)\. EachBinarySearchStepnarrows the search for the most recent step that wrote to the current position, matching one additional bit of the step number per layer\. The step\-number bits of the best match accumulate inscr3\.
7. 7\.Get Last Written Symbol\(self\-attention, Claim C\.6\)\. Using the step number identified by binary search, retrieves the symbol written at that step, storing it inscr1\.
8. 8\.Get Initial Symbol\(cross\-attention, Lemma C\.7\)\. The single cross\-attention layer: the decoder queries the encoderEEby matchingpos3against the position indices inEE, retrieving the original tape symbol\. Result stored inscr2\.
9. 9\.Assemble Symbol\(feedforward, Lemma C\.8\)\. Three operations \(GetV,ArrangeSymbols,CombineSymbols\) implement a priority: \(a\) if the position was previously written to, use the last written symbol fromscr1; \(b\) else if the position is on the original tape, use the initial symbol fromscr2; \(c\) else use the empty symbolEE\. The result is written tosym1andpos3is copied topos2, preparing the vector for the next step\.

![Refer to caption](https://arxiv.org/html/2605.08150v1/img/wcm_network_paper.png)Figure 2:Architecture of the WCM21 simulator for one step\. Feedforward \(FF\) layers implement Boolean circuits; self\-attention layers search the decoder history; cross\-attention reads the original tape from the encoder\.
### 5\.3Attention Mechanism

All attention layers use the same functional form\. Given query matrixQQ, key matrixKK, and value matrixVV\(obtained by linear projections with specified weights\), plus a null keyk0k\_\{0\}and null valuev0v\_\{0\}:

Attn​\(Q,K,V\)=softmax​\(κ​Q​K⊤\)​V,\\mathrm\{Attn\}\(Q,K,V\)=\\mathrm\{softmax\}\(\\kappa\\,QK^\{\\top\}\)V,\(3\)whereκ=9999\\kappa=9999approximates hard attention\. The null key\-value pair provides a default output when no key matches the query\.

The query and key projections are designed so that matching positions produce a high dot product \(equal to the number of matching binary bits\), while non\-matching positions score lower\. With the large temperature, softmax concentrates all weight on the best match, effectively implementing exact lookup\.

The network contains three types of attention: 9 self\-attention layers \(1 for visited\-position detection,⌈log2⁡T⌉\\lceil\\log\_\{2\}T\\rceilfor binary search, 1 for symbol retrieval\), all attending over the decoder historyHH; and 1 cross\-attention layer, where the decoder queries the encoderEE\.

### 5\.4Complexity

For a Turing machine with\|Q\|\|Q\|states,\|Γ\|\|\\Gamma\|symbols, and maximum stepsTT: the transition layer hasO​\(\|Q\|​\|Γ\|\)O\(\|Q\|\\,\|\\Gamma\|\)hidden neurons; the adder chain and binary search each haveO​\(log⁡T\)O\(\\log T\)layers; each state vector has widthO​\(\|Q\|\+\|Γ\|\+log⁡T\)O\(\|Q\|\+\|\\Gamma\|\+\\log T\); and the decoder history grows linearly withTT\.

## 6The SS95 Construction

The Siegelmann\-Sontag construction\[[8](https://arxiv.org/html/2605.08150#bib.bib8),[9](https://arxiv.org/html/2605.08150#bib.bib9)\]takes a fundamentally different approach: it reformulates the Turing machine as a*stack machine*and encodes each stack as a single rational number\.

### 6\.1Stack Machines

App\-stack machine is equivalent to a Turing machine but usesppstacks \(each supporting push, pop, and peek\) instead of a tape\. For the balanced parentheses problem, two stacks suffice: stack 0 holds the unprocessed input; stack 1 accumulates unmatched open parentheses\. The transition function maps\(state,top0,top1\)\(\\text\{state\},\\text\{top\}\_\{0\},\\text\{top\}\_\{1\}\)to\(next state,op0,op1\)\(\\text\{next state\},\\text\{op\}\_\{0\},\\text\{op\}\_\{1\}\), where each operation is one ofnoop,push 0,push 1, orpop\.

### 6\.2Cantor\-Set Encoding

The key mathematical trick is encoding each stack by a rational number\. For a binary stack \(symbols0and11\) with basebband parameterρ\\rho, the encoding is:

ℰ​\(a1​a2​⋯​ak\)=∑i=1kb−1\+4​ρ​\(ai−1\)bi\.\\mathcal\{E\}\(a\_\{1\}a\_\{2\}\\cdots a\_\{k\}\)=\\sum\_\{i=1\}^\{k\}\\frac\{b\-1\+4\\rho\(a\_\{i\}\-1\)\}\{b^\{i\}\}\.\(4\)Withb=4b=4andρ=1/2\\rho=1/2, symbol0maps to1/41/4and11maps to3/43/4of each interval, corresponding to a Cantor set in\[0,1\]\[0,1\]\. The empty stack maps to0\.

Note thata1a\_\{1\}is the top of the stack andaka\_\{k\}, the bottom, reversed from how stacks are written in Python\.

push, pop, and peek are linear functionsof the encoded value\. Withb=4b=4andρ=1/2\\rho=1/2,

push​\(v,a\)\\displaystyle\\mathrm\{push\}\(v,a\)=v\+2​a\+14,\\displaystyle=\\frac\{v\+2a\+1\}\{4\},\(5\)pop​\(v\)\\displaystyle\\mathrm\{pop\}\(v\)=4​v−2​top​\(v\)−1,\\displaystyle=4v\-2\\,\\mathrm\{top\}\(v\)\-1,\(6\)top​\(v\)\\displaystyle\\mathrm\{top\}\(v\)=\{0if​σ​\(2​v−1\)=0,1otherwise\.\\displaystyle=\\begin\{cases\}0&\\text\{if \}\\sigma\(2v\-1\)=0,\\\\ 1&\\text\{otherwise\.\}\\end\{cases\}\(7\)Since these are linear or piecewise\-linear, a network with the saturated activationσ​\(x\)=clamp⁡\(x,0,1\)\\sigma\(x\)=\\operatorname\{clamp\}\(x,\\,0,\\,1\)can manipulate stacks using only matrix multiplications and element\-wise clamping\.

![Refer to caption](https://arxiv.org/html/2605.08150v1/img/cantor_set_paper.png)Figure 3:Cantor set encodings by stack length\. Each stack symbol selects a subinterval, and the stack is represented by a single rational number in\[0,1\]\[0,1\]\. Push divides bybb; pop multiplies bybb\.
### 6\.3Network Architecture

The network maintains a state vector containing the one\-hot machine state and the Cantor\-encoded value of each stack\. At each step, a*configuration detector*identifies the matching transition rule from the current state and the top of each stack, then applies the corresponding stack operations\.

The weights connecting the configuration detector to the output layer are determined by solving a linear system\. Letd∈ℝ\|Q\|⋅3pd\\in\\mathbb\{R\}^\{\|Q\|\\cdot 3^\{p\}\}be the detector output \(one entry per state–stack\-top combination\)\. The next\-state vector isβ​d\\beta\\,dand the stack\-operation vector isγ​d\\gamma\\,d, where the matricesβ\\betaandγ\\gammaare obtained by solving least squares against the desired outputs for all possible configurations\.

Two versions are implemented:

#### 4\-layer version \(version=4\)\.

Each Turing machine step uses 4 network layers in an explicit pipeline: layer F4 reads the configuration \(state and stack tops\), F3 detects which transition rule matches, F2 applies the transition \(next state and stack operations\), and F1 reassembles the output vector\. Usesb=4b=4,ρ=1/2\\rho=1/2, andfloat32arithmetic\.

#### 1\-layer version \(version=1\)\.

A single recurrent layer per step, following the original construction more closely\. Usesb=10​p2b=10p^\{2\}, givingb=40b=40forp=2p=2\. Using afloat64stack, which has 53 bits of mantissa, each pop amplifies rounding error by a factor ofbb\. Afterkkpops the accumulated error is∼bk⋅2−53\\sim b^\{k\}\\cdot 2^\{\-53\}, giving⌊53/log2⁡40⌋=9\\lfloor 53/\\log\_\{2\}40\\rfloor=9reliable pops\. This is enough for balanced\-parenthesis inputs of length 8 \(4 matched pairs\)\.

## 7Implementation

The package is implemented in Python using PyTorch\[[6](https://arxiv.org/html/2605.08150#bib.bib6)\]\. The interface requires only a transition function and terminal states:

1fromturing\.wcm\.simulatorimportDescription,Simulator

2

3desc=Description\(transition\_function,terminal\_states\)

4sim=Simulator\(desc,T=100\)

5result=sim\.simulate\("B\(\)\(\(\(\)\(\(\)\)\)\(\)\)E"\)

6

Listing 2:Simulating with the WCM21 transformer\.1fromturing\.ss\.simulatorimportDescription,Simulator

2

3desc=Description\(delta\_stack,terminal\_states\)

4sim4=Simulator\(desc,version=4\)

5sim4\.simulate\("\(\(\)\(\)\)",T=12\)

6

7sim1=Simulator\(desc,version=1\)

8sim1\.simulate\("\(\(\)\)",T=12\)

Listing 3:Simulating with the SS95 stack machine\.Both simulators produce standardtorch\.nn\.Moduleobjects\. The WCM21 model for the balanced parentheses example \(6 states, 5 symbols,T=100T=100\) has embedding widthw=59w=59and consists of: aTransitionmodule \(59→89→5959\\to 89\\to 59\), aPreprocessForAdder\(59→6659\\to 66\), 7FullAddermodules \(each with 2HalfAddersubmodules and 2 OR layers\), aProjectDown\(66→5966\\to 59\), 9 self\-attention layers \(1 for position detection, 7 for binary search, 1 for symbol retrieval\), 1 cross\-attention layer \(for reading the original tape\), and 3 feedforward layers for symbol assembly\. All feedforward layers useReLU\\mathrm\{ReLU\}; all attention layers use softmax withκ=9999\\kappa=9999\.

Interactive Jupyter notebooks are included:part1builds the transition layer and binary adder from scratch;part2demonstrates the full pipeline with attention\.

## 8Discussion

#### Interpretability and permutation symmetry\.

These networks are interpretable by construction: every weight has a known function\. This interpretability does not transfer to networks trained by gradient descent\. A trained network implementing the same function may have its neurons permuted, rescaled, and entangled\. WithHHhidden neurons, that’sH\!H\!permutations, placing a fundamental limit on post\-hoc mechanistic interpretability\.

#### Numerical precision\.

The WCM21 construction operates on binary values in\{0,1\}\\\{0,1\\\}and is numerically exact infloat32\. The SS95 construction is more delicate: the Cantor encoding stores information in increasingly small fractional digits, and pop amplifies error by a factor ofbbper step\. The 4\-layer variant \(b=4b=4\) is stable for typical inputs; the 1\-layer variant \(b=40b=40\) requiresfloat64and degrades after approximately 8 pops\. This precision\-computability tradeoff is inherent to Siegelmann\-Sontag and illustrates the gap between theoretical Turing completeness and practical computation\.

#### Future work\.

As standard PyTorch modules, the models can serve as initializations for gradient\-based optimization\. Open questions include: How flat is the loss landscape around the constructed solution, and how much weight perturbation can the simulation tolerate? Does fine\-tuning on specific input distributions yield shortcuts that the general construction misses?

## 9Conclusion

We have presented a constructive approach to compiling Turing machines into neural network weights\. Starting from Boolean gates in ReLU networks, we built up through DNF realization, binary adders, and hard attention to obtain two Turing machine simulators: a transformer \(WCM21\) and a recurrent network \(SS95\)\. The resulting PyTorch package takes a Turing machine description and produces a model that is correct by construction, with no training required\. Code is available at[https://github\.com/jonrbates/turing](https://github.com/jonrbates/turing)\.

## References

- Bhattamishra et al\. \[2020\]S\. Bhattamishra, K\. Ahuja, and N\. Goyal\.On the computational power of transformers and its implications in sequence modeling\.In*Proceedings of the 24th Conference on Computational Natural Language Learning*, pp\. 455–475, 2020\.
- Graves et al\. \[2014\]A\. Graves, G\. Wayne, and I\. Danihelka\.Neural Turing machines\.*arXiv preprint arXiv:1410\.5401*, 2014\.
- Li et al\. \[2024\]Z\. Li, T\. Wang, and Y\. Yu\.Chain of thought empowers transformers to solve inherently serial problems\.In*The Twelfth International Conference on Learning Representations \(ICLR\)*, 2024\.
- Li and Wang \[2025\]Q\. Li and Y\. Wang\.Constant bit\-size transformers are Turing complete\.In*Advances in Neural Information Processing Systems \(NeurIPS\)*, 2025\.
- Merrill and Sabharwal \[2024\]W\. Merrill and A\. Sabharwal\.The expressive power of transformers with chain of thought\.In*The Twelfth International Conference on Learning Representations \(ICLR\)*, 2024\.
- Paszke et al\. \[2019\]A\. Paszke, S\. Gross, F\. Massa, A\. Lerer, J\. Bradbury, G\. Chanan, T\. Killeen, Z\. Lin, N\. Gimelshein, L\. Antiga, et al\.PyTorch: An imperative style, high\-performance deep learning library\.In*Advances in Neural Information Processing Systems*, 2019\.
- Pérez et al\. \[2021\]J\. Pérez, J\. Barceló, and F\. Marinkovic\.Attention is Turing\-complete\.*Journal of Machine Learning Research*, 22\(75\):1–35, 2021\.
- Siegelmann and Sontag \[1992\]H\. T\. Siegelmann and E\. D\. Sontag\.On the computational power of neural nets\.In*Proceedings of the 5th Annual ACM Conference on Computational Learning Theory \(COLT\)*, pp\. 440–449, 1992\.
- Siegelmann and Sontag \[1995\]H\. T\. Siegelmann and E\. D\. Sontag\.On the computational power of neural nets\.*Journal of Computer and System Sciences*, 50\(1\):132–150, 1995\.
- Smolensky et al\. \[2024\]P\. Smolensky, R\. Fernandez, Z\. H\. Zhou, M\. Opper, A\. Davies, and J\. Gao\.Mechanisms of symbol processing for in\-context learning in transformer networks\.*arXiv preprint arXiv:2410\.17498*, 2024\.
- Wei et al\. \[2021\]C\. Wei, Y\. Chen, and T\. Ma\.Statistically meaningful approximation: a case study on approximating Turing machines with transformers\.*arXiv preprint arXiv:2107\.13163*, 2021\.