Softmax Transformers are Turing-Complete

2025/11/25 by Jiang, Hongjian, Hahn, Michael, Zetzsche, Georg +1 · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2511.20038

Abstract

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.

Citations

• Quantitative Bounds for Length Generalization in Transformers
• Non-Asymptotic Length Generalization
• Constant Bit-size Transformers Are Turing Complete
• Simulating Hard Attention Using Soft Attention
• A Formal Framework for Understanding Length Generalization in Transformers
• Universal Length Generalization with Turing Programs
• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
• Logical Languages Accepted by Transformer Encoders with Hard Attention
• Overcoming a Theoretical Limitation of Self-Attention
• BNAI, NO-TOKEN, and MIND-UNITY: Pillars of a Systemic Revolution in Artificial Intelligence
• Inductive Biases and Variable Creation in Self-Attention Mechanisms
• Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation
• Thinking Like Transformers
• Relative Positional Encoding for Transformers with Linear Complexity
• RoFormer: Enhanced Transformer with Rotary Position Embedding
• Position Information in Transformers: An Overview
• Position Information in Transformers: An Overview
• mT5: A massively multilingual pre-trained text-to-text transformer
• On the Computational Power of Transformers and its Implications in\n Sequence Modeling
• DeBERTa: Decoding-enhanced BERT with Disentangled Attention
• Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context
• Self-Attention with Relative Position Representations
• Attention Is All You Need
• The Expressive Power of Transformers with Chain of Thought
• Ask, and it shall be given: On the Turing completeness of prompting

Cited by

• A model of errors in transformers

Related

• Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
• Constant Bit-size Transformers Are Turing Complete
• Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
• Transformers are Inherently Succinct
• The Expressive Power of Transformers with Chain of Thought