EPS
← All batches·2605.08150

A PyTorch Library of Turing-Complete Neural Networks

topic: general_aitop score: 100released: 2026-05-12first surfaced: 2026-05-12arXivPDFlinked_to_results2026-05-12

Authors: Jonathan Bates

arXiv · PDF

Summary

This paper presents a PyTorch library that compiles exact Turing machines into neural networks—no training required. You provide a transition function and terminal states, and the library builds either a Transformer (with attention and feedforward layers) or a recurrent network (encoding the stack in a Cantor set) whose forward pass corresponds to one step of the Turing machine. The code shows how ReLU networks implement Boolean logic gates and how hard attention implements positional lookup, serving as a runnable reference for the symbolic-neural bridge.

Main takeaways:

  • The library constructs neural networks that exactly simulate a given Turing machine, producing weights directly from the transition table with no training.
  • Two architectures: a Transformer based on hard attention (Wei et al. 2021) and a recurrent net encoding the stack via Cantor-set encoding (Siegelmann & Sontag 1995).
  • ReLU layers implement Boolean gates (AND, OR, NOT, XOR) and compose them into circuits; hard attention implements tape lookups.
  • Intended as a reference for understanding symbolic computation in neural form and a testbed for studying stability of constructed solutions under gradient descent.

Relevance

Tangentially relevant to my installation-path equivalence work—this is extreme case of "installing" behavior (a Turing machine) via direct weight construction rather than prompting, steering, or fine-tuning. It could inform the limits of what counts as "behavioral installation," but it's not directly about persona or conditional behavior.

Abstract

arXiv:2605.08150v1 Announce Type: new 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.