# Constant Bit-size Transformers Are Turing Complete

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 22 May 2025.

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

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [The Parallelism Tradeoff: Limitations of Log-Precision Transformers](https://mlsanity.com/paper/2207.00729/) (2022)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers](https://mlsanity.com/paper/2503.03961/) (2025)
- [Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages](https://mlsanity.com/paper/2310.13897/) (2023)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theory](https://mlsanity.com/paper/2405.16674/) (2024)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)

## Built on by (most cited first, 19 of 19)

- [A Survey on Latent Reasoning](https://mlsanity.com/paper/2507.06203/) (2025)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (2025)
- [Is In-Context Learning Learning?](https://mlsanity.com/paper/2509.10414/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [Neural Weight Norm = Kolmogorov Complexity](https://mlsanity.com/paper/2605.10878/) (2026)
- [A model of errors in transformers](https://mlsanity.com/paper/2601.14175/) (2026)
- [A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention](https://mlsanity.com/paper/2602.01763/) (2026)
- [No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guarantees](https://mlsanity.com/paper/2603.08761/) (2026)
- [The Library Theorem: How External Organization Governs Agentic Reasoning Capacity](https://mlsanity.com/paper/2603.21272/) (2026)
- [Transformer Circuits Can Realize Clustering Algorithms](https://mlsanity.com/paper/2506.19125/) (2025)
- [Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchy](https://mlsanity.com/paper/2604.02709/) (2026)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [A PyTorch Library of Turing-Complete Neural Networks](https://mlsanity.com/paper/2605.08150/) (2026)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete](https://mlsanity.com/paper/2606.01532/) (2026)
- [Planning with Transformers: Chain of Computation and Structured Context Windows](https://mlsanity.com/paper/2607.17710/) (2026)
- [Understanding Generalization Requires Universal Induction](https://mlsanity.com/paper/2609.34458/) (2026)

## Abstract (arXiv)

We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This improves previous works, which require scaling up either the model's precision or the number of parameters on longer inputs. Furthermore, we prove that the complexity class SPACE[s(n)] exactly characterizes the expressive power of a constant bit-size transformer with a context window of length s(n). Our approach relies on simulating Post machines, a Turing-complete computational model. Post machines can be modeled as automata equipped with a queue, exhibiting computational behaviors naturally aligned with those of transformers. The behavioral similarity between transformers and Post machines may offer new insights into the mechanisms underlying the reasoning abilities of transformers.