# A PyTorch Library of Turing-Complete Neural Networks

arXiv: https://arxiv.org/abs/2605.08150 · HTML: https://mlsanity.com/paper/2605.08150/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 17 references that are in the map.
- First posted on arXiv 3 May 2026.

## Builds on (most cited first, 7 of 7)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Mechanisms of Symbol Processing for In-Context Learning in Transformer Networks](https://mlsanity.com/paper/2410.17498/) (2024)

## Abstract (arXiv)

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.