Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management
The paper discusses the Turing-completeness of autoregressive Transformers, emphasizing the importance of context management. It distinguishes between two settings: a fixed Transformer system and a scaling-family setting. The authors argue that context management critically influences the computational power of these models in real-world applications.
- ▪The paper formalizes the fixed-system setting for autoregressive Transformers.
- ▪It clarifies that existing proofs of Turing-completeness often rely on a scaling-family setting.
- ▪Different context-management methods can significantly affect the computational capabilities of Transformers.
Opening excerpt (first ~120 words) tap to expand
Computer Science > Artificial Intelligence arXiv:2605.19514 (cs) [Submitted on 19 May 2026] Title:Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management Authors:Guanyu Cui, Zhewei Wei, Kun He View a PDF of the paper titled Position: The Turing-Completeness of Real-World Autoregressive Transformers Relies Heavily on Context Management, by Guanyu Cui and 2 other authors View PDF HTML (experimental) Abstract:Many works make the eye-catching claim that Transformers are Turing-complete.
…
Excerpt limited to ~120 words for fair-use compliance. The full article is at arXiv cs.AI.
Discussion
0 commentsMore from arXiv cs.AI
