Skip to content

README.md

Latest commit

 

History

History
135 lines (98 loc) · 4.4 KB

README.md

File metadata and controls

135 lines (98 loc) · 4.4 KB
Raw

Turing

Simulate Turing machines with neural networks. No training required. Weights are set analytically from the machine description.

Two simulators are available, each implementing a different theoretical result:

🚀 Quick Start

Install

git clone https://github.com/jonrbates/turing.git
cd turing
# requires python3.10+
python3 -m venv .venv
source .venv/bin/activate
pip install --upgrade pip
# CPU-only PyTorch (skip the GPU wheels)
pip install "torch>=2.1" --index-url https://download.pytorch.org/whl/cpu
pip install -e .

Run the WCM simulator

from turing.wcm.simulator import Description, Simulator

# Description() defaults to the balanced parentheses machine
tx = Simulator(Description(), T=100)
tx.simulate("B()((()(()))())E")

Example: The Balanced Parentheses Problem

We want to determine whether a string of parentheses is balanced; e.g. "(())" is balanced but "())" is not.

A Turing machine solves this by reading the tape "B()((()(()))())E" (where B and E mark the ends). The machine has a head that starts at B and moves left or right, reading and writing symbols according to its rules. The head position is shown as ^:

turing machine solving balanced parentheses

The machine has a discrete internal state (I, R, M, V, T, F in the animation). Its behavior is fully defined by a transition function $\delta$: given the current state and symbol under the head, $\delta$ outputs (1) the symbol to write, (2) the next state, and (3) which direction to move.

We can visualize $\delta$ as a directed graph. States are vertices; edges are transitions. The initial state is a diamond; terminal states are squares.

turing machine transition graph for balanced parentheses

The machine halts when it reaches a terminal state (T = balanced, F = not balanced).

Defining the transition function in Python:

transition_function = {
    ("I", "B") : ("R", "B",  1),
    ("R", "(") : ("R", "(",  1),
    ("R", ")") : ("M", "*", -1),
    ("R", "*") : ("R", "*",  1),
    ("R", "E") : ("V", "E", -1),
    ("M", "B") : ("F", "*", -1),
    ("M", "(") : ("R", "*",  1),
    ("M", "*") : ("M", "*", -1),
    ("V", "(") : ("F", "*", -1),
    ("V", "*") : ("V", "*", -1),
    ("V", "B") : ("T", "B",  1),
}

terminal_states = ["T", "F"]

Each entry maps (state, symbol) → (next_state, write_symbol, direction) where direction is +1 (right) or -1 (left).

Simulating with the WCM neural network:

from turing.wcm.simulator import Description, Simulator

description = Description(transition_function, terminal_states)
tx = Simulator(description, T=100)
tape = "B()((()(()))())E"
tx.simulate(tape)
# prints each step and returns "T" (balanced) or "F" (not balanced)

Simulator(description, T=100) constructs a PyTorch model and analytically sets its weights to simulate the given Turing machine without any training. T is the maximum number of steps.

📓 Notebooks

The notebooks/ directory contains interactive walkthroughs:

  • balanced_parentheses_part1.ipynb - build the transition layer from scratch, step through the balanced parentheses problem
  • balanced_parentheses_part2.ipynb - full WCM simulation, inspect the network's internal state at each step

Paper-to-code mapping

Paper Code What it implements
WCM21 src/turing/wcm/ Transformer-style TM simulator
SS95, §4 src/turing/ss/ version=4 4-layer RNN TM simulator
SS95, §1 src/turing/ss/ version=1 1-layer RNN TM simulator

Citation

@misc{bates2026turing,
  author        = {Jonathan Bates},
  title         = {A {PyTorch} Library of {Turing}-Complete Neural Networks},
  year          = {2026},
  eprint        = {2605.08150},
  archivePrefix = {arXiv},
}