mlsanityData to 13 Oct 2026

Efficient Turing Machine Simulation with Transformers

arXiv 2512.00003 ↗First posted 28 Sep 2025cs.CC cs.DS cs.LGcited by 4

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

Constant bit-size Transformers are known to be Turing complete, but existing constructions require Omega(s(n)) chain-of-thought (CoT) steps per simulated Turing machine (TM) step, leading to impractical reasoning lengths. In this paper, we significantly reduce this efficiency gap by proving that any (t(n),s(n))-bounded multi-tape TM can be simulated by a constant bit-size Transformer with an optimal O(s(n))-long context window and only O(s(n)c) CoT steps per TM step, where c>0 can be made arbitrarily small by letting the Transformers' head-layer product sufficiently large. In addition, our construction shows that sparse attention with fixed geometric offsets suffices for efficient universal computation. Our proof leverages multi-queue TMs as a bridge. The main technical novelty is a more efficient simulation of multi-tape TMs by synchronous multi-queue TMs, improving both time and space complexity under stricter model assumptions.

Key facts. Cited by 4 papers in the map (data through 13 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 39 of its 58 references that are in the map. First posted on arXiv 28 Sep 2025.

Builds on

39 of 58 references.

Closest ancestors · 10

Same direction, newest first

  1. 2025PENCIL: Long Thoughts with Short Memory18 Mar
  2. 2025Small Models Struggle to Learn from Strong Reasoners17 Feb
  3. 2025When More is Less: Understanding Chain-of-Thought Length in LLMs11 Feb
  4. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers4 Feb
  5. 2024Training Large Language Models to Reason in a Continuous Latent Space9 Dec
  6. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb
  7. 2024The Impact of Reasoning Step Length on Large Language Models10 Jan
  8. 2023Mixed Distillation Helps Smaller Language Model Better Reasoning17 Dec
  9. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective24 May
  10. 2022A Logic for Expressing Log-Precision Transformers6 Oct

Other references · 29

  1. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,247
  2. 2023GPQA: A Graduate-Level Google-Proof Q&A Benchmarkcited by 2,804
  3. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,137
  4. 2018Self-Attention with Relative Position Representationscited by 1,116
  5. 2021Transformers in Vision: A Surveycited by 1,010
  6. 2019Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecastingcited by 607
  7. 2024Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMscited by 568
  8. 2025Stop Overthinking: A Survey on Efficient Reasoning for Large Language Modelscited by 461
  9. 2025L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learningcited by 382
  10. 2024MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attentioncited by 378
  11. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 287
  12. 2025O1-Pruner: Length-Harmonizing Fine-Tuning for O1-Like Reasoning Pruningcited by 278
17 more
  1. 2025TokenSkip: Controllable Chain-of-Thought Compression in LLMscited by 248
  2. 2025CoT-Valve: Length-Compressible Chain-of-Thought Tuningcited by 167
  3. 2023What Formal Languages Can Transformers Express? A Surveycited by 121
  4. 2023SparQ Attention: Bandwidth-Efficient LLM Inferencecited by 118
  5. 2025Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoningcited by 118
  6. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  7. 2025Efficient Reasoning Models: A Surveycited by 94
  8. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  9. 2025Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoningcited by 88
  10. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  11. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 65
  12. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformerscited by 50
  13. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 48
  14. 2024Theoretical limitations of multi-layer Transformercited by 45
  15. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 37
  16. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  17. 2025PowerAttention: Exponentially Scaling of Receptive Fields for Effective Sparse Attentioncited by 8

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Neural Weight Norm = Kolmogorov Complexitycited by 2
  2. 2026Loom: A Scalable Analytical Neural Computer Architecturecited by 0
  3. 2026Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Completecited by 0
  4. 2026Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcriptscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
  2. 2026The Expressive Power of Low Precision Softmax Transformers with (Summarized) Chain-of-Thought
  3. 2026Efficiently Representing Algorithms With Chain-of-Thought Transformers
  4. 2022Transformers Learn Shortcuts to Automata
  5. 2025Exact Expressive Power of Transformers with Padding
  6. 2025Softmax Transformers are Turing-Complete
  7. 2024Universal Length Generalization with Turing Programs
  8. 2026Fixed Universal Transformers