mlsanityData to 14 Oct 2026

Constant Bit-size Transformers Are Turing Complete

arXiv 2506.12027 ↗First posted 22 May 2025cs.CC cs.LGcited by 19

Not on the map. Why?

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.

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

16 of 37 references.

References · 16

  1. 2023GPT-4 Technical Reportcited by 18,396
  2. 2024The Llama 3 Herd of Modelscited by 14,715
  3. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,371
  4. 2023SWE-bench: Can Language Models Resolve Real-World GitHub Issues?cited by 3,373
  5. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,879
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  8. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  9. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  10. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  11. 2023The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learningcited by 63
  12. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 53
4 more
  1. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  2. 2025PENCIL: Long Thoughts with Short Memorycited by 33
  3. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  4. 2024Autoregressive Large Language Models are Computationally Universalcited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 7; 2026: 12.

19 papers.

Sort:

By area:

  1. 2025A Survey on Latent Reasoningcited by 81
  2. 2025Softmax Transformers are Turing-Completecited by 9
  3. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  4. 2025Efficient Turing Machine Simulation with Transformerscited by 4
  5. 2025Is In-Context Learning Learning?cited by 2
  6. 2025Probability Distributions Computed by Autoregressive Transformerscited by 2
  7. 2026Neural Weight Norm = Kolmogorov Complexitycited by 2
  8. 2026A model of errors in transformerscited by 1
  9. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1
  10. 2026No Certificate for Alignment: Two Independent Impossibilities and the Pareto Frontier of Achievable Safety Guaranteescited by 1
  11. 2026The Library Theorem: How External Organization Governs Agentic Reasoning Capacitycited by 1
  12. 2025Transformer Circuits Can Realize Clustering Algorithmscited by 0
7 more
  1. 2026Evaluating the Formal Reasoning Capabilities of Large Language Models through Chomsky Hierarchycited by 0
  2. 2026Loom: A Scalable Analytical Neural Computer Architecturecited by 0
  3. 2026A PyTorch Library of Turing-Complete Neural Networkscited by 0
  4. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  5. 2026Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Completecited by 0
  6. 2026Planning with Transformers: Chain of Computation and Structured Context Windowscited by 0
  7. 2026Understanding Generalization Requires Universal Inductioncited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Transformers Learn Shortcuts to Automata
  2. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  3. 2026Fixed Universal Transformers
  4. 2025Transformers are Inherently Succinct
  5. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
  6. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity
  7. 2023The Expressive Power of Transformers with Chain of Thought
  8. 2025Exact Expressive Power of Transformers with Padding