mlsanityData to 14 Oct 2026

Softmax Transformers are Turing-Complete

arXiv 2511.20038 ↗First posted 25 Nov 2025cs.FL cs.LG cs.LOcited by 9

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

Abstract (arXiv)

Hard attention Chain-of-Thought (CoT) transformers are known to be Turing-complete. However, it is an open problem whether softmax attention Chain-of-Thought (CoT) transformers are Turing-complete. In this paper, we prove a stronger result that length-generalizable softmax CoT transformers are Turing-complete. More precisely, our Turing-completeness proof goes via the CoT extension of the Counting RASP (C-RASP), which correspond to softmax CoT transformers that admit length generalization. We prove Turing-completeness for CoT C-RASP with causal masking over a unary alphabet (more generally, for letter-bounded languages). While we show this is not Turing-complete for arbitrary languages, we prove that its extension with relative positional encoding is Turing-complete for arbitrary languages. We empirically validate our theory by training transformers for languages requiring complex (non-linear) arithmetic reasoning.

Key facts. Cited by 9 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 24 of its 30 references that are in the map. First posted on arXiv 25 Nov 2025.

Builds on

24 of 30 references.

Closest ancestors · 1

Same direction, newest first

  1. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Models28 Jan

Other references · 23

  1. 2017Attention Is All You Needcited by 60,361
  2. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  3. 2020DeBERTa: Decoding-enhanced BERT with Disentangled Attentioncited by 2,181
  4. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  5. 2020mT5: A massively multilingual pre-trained text-to-text transformercited by 1,818
  6. 2018Self-Attention with Relative Position Representationscited by 1,120
  7. 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
  8. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  9. 2021Thinking Like Transformerscited by 184
  10. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  11. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  12. 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
11 more
  1. 2021Position Information in Transformers: An Overviewcited by 103
  2. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  3. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
  4. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
  5. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38
  6. 2021Relative Positional Encoding for Transformers with Linear Complexitycited by 37
  7. 2024Universal Length Generalization with Turing Programscited by 25
  8. 2025Constant Bit-size Transformers Are Turing Completecited by 19
  9. 2024Simulating Hard Attention Using Soft Attentioncited by 15
  10. 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
  11. 2025Non-Asymptotic Length Generalizationcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 9.

9 papers.

  1. 2026On the Spatiotemporal Dynamics of Generalization in Neural Networkscited by 3
  2. 2026On the Ability of Transformers to Verify Planscited by 2
  3. 2026Indexing: the Beginning and the Endcited by 2
  4. 2026A model of errors in transformerscited by 1
  5. 2026Synthesis and Verification of Transformer Programs (Technical Report)cited by 0
  6. 2026On the Mirage of Long-Range Dependency, with an Application to Integer Multiplicationcited by 0
  7. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  8. 2026Planning with Transformers: Chain of Computation and Structured Context Windowscited by 0
  9. 2026On the Expressive Power of Transformerscited 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. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems
  4. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
  5. 2025Transformers are Inherently Succinct
  6. 2025A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers
  7. 2026Efficiently Representing Algorithms With Chain-of-Thought Transformers
  8. 2025To CoT or To Loop? A Formal Comparison Between Chain-of-Thought and Looped Transformers