# Efficient Turing Machine Simulation with Transformers

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

## Key facts

- Cited by 4 papers in the map (data through 14 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.

## Placed in

- LLM reasoning / [Prompting and chain-of-thought reasoning](https://mlsanity.com/lr/prompting-and-chain-of-thought-reasoning/)

## Builds on (most cited first, 30 of 39)

- [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Transformers in Vision: A Survey](https://mlsanity.com/paper/2101.01169/) (2021)
- [Training Large Language Models to Reason in a Continuous Latent Space](https://mlsanity.com/paper/2412.06769/) (2024)
- [Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting](https://mlsanity.com/paper/1907.00235/) (2019)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [L1: Controlling How Long A Reasoning Model Thinks With Reinforcement Learning](https://mlsanity.com/paper/2503.04697/) (2025)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [O1-Pruner: Length-Harmonizing Fine-Tuning for O1-Like Reasoning Pruning](https://mlsanity.com/paper/2501.12570/) (2025)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [TokenSkip: Controllable Chain-of-Thought Compression in LLMs](https://mlsanity.com/paper/2502.12067/) (2025)
- [When More is Less: Understanding Chain-of-Thought Length in LLMs](https://mlsanity.com/paper/2502.07266/) (2025)
- [CoT-Valve: Length-Compressible Chain-of-Thought Tuning](https://mlsanity.com/paper/2502.09601/) (2025)
- [The Impact of Reasoning Step Length on Large Language Models](https://mlsanity.com/paper/2401.04925/) (2024)
- [What Formal Languages Can Transformers Express? A Survey](https://mlsanity.com/paper/2311.00208/) (2023)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [Towards Thinking-Optimal Scaling of Test-Time Compute for LLM Reasoning](https://mlsanity.com/paper/2502.18080/) (2025)
- [Small Models Struggle to Learn from Strong Reasoners](https://mlsanity.com/paper/2502.12143/) (2025)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexity](https://mlsanity.com/paper/2204.06618/) (2022)
- [Token Assorted: Mixing Latent and Text Tokens for Improved Language Model Reasoning](https://mlsanity.com/paper/2502.03275/) (2025)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)

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

- [Neural Weight Norm = Kolmogorov Complexity](https://mlsanity.com/paper/2605.10878/) (2026)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete](https://mlsanity.com/paper/2606.01532/) (2026)
- [Transcript-Managed Transformers: Monotone Multi-Agent Collapse and Universality with Two Pop-Enabled Transcripts](https://mlsanity.com/paper/2607.29496/) (2026)

## 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.