# Autoregressive Large Language Models are Computationally Universal

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 4 Oct 2024.

## Builds on (most cited first, 23 of 23)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Universal Transformers](https://mlsanity.com/paper/1807.03819/) (2018)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Augmented Language Models: a Survey](https://mlsanity.com/paper/2302.07842/) (2023)
- [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)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [Learning to Transduce with Unbounded Memory](https://mlsanity.com/paper/1506.02516/) (2015)
- [Memory Augmented Large Language Models are Computationally Universal](https://mlsanity.com/paper/2301.04589/) (2023)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [Neural Random-Access Machines](https://mlsanity.com/paper/1511.06392/) (2015)
- [Recurrent Neural Networks as Weighted Language Recognizers](https://mlsanity.com/paper/1711.05408/) (2017)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [GPT is becoming a Turing machine: Here are some ways to program it](https://mlsanity.com/paper/2303.14310/) (2023)

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

- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Stable-DiffCoder: Pushing the Frontier of Code Diffusion Large Language Model](https://mlsanity.com/paper/2601.15892/) (2026)
- [K2-Think: A Parameter-Efficient Reasoning System](https://mlsanity.com/paper/2509.07604/) (2025)
- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)
- [Memory makes computation universal, remember?](https://mlsanity.com/paper/2412.17794/) (2024)
- [Recursive Inference Machines for Neural Reasoning](https://mlsanity.com/paper/2603.05234/) (2026)
- [Exact Learning of Arithmetic with Differentiable Agents](https://mlsanity.com/paper/2511.22751/) (2025)
- [Universal computation is intrinsic to language model decoding](https://mlsanity.com/paper/2601.08061/) (2026)
- [Efficient Diffusion LLMs via Temporal-Spatial Parallel Decoding and Confidence Extrapolation](https://mlsanity.com/paper/2605.30753/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Understanding LLM Failures: A Multi-Tape Turing Machine Analysis of Systematic Errors in Language Model Reasoning](https://mlsanity.com/paper/2602.15868/) (2026)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [TRACES: Tagging Reasoning Steps for Adaptive Cost-Efficient Early-Stopping](https://mlsanity.com/paper/2604.21057/) (2026)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [APEX: Speculate smarter, not deeper](https://mlsanity.com/paper/2610.07780/) (2026)

## Abstract (arXiv)

We show that autoregressive decoding of a transformer-based language model can realize universal computation, without external intervention or modification of the model's weights. Establishing this result requires understanding how a language model can process arbitrarily long inputs using a bounded context. For this purpose, we consider a generalization of autoregressive decoding where, given a long input, emitted tokens are appended to the end of the sequence as the context window advances. We first show that the resulting system corresponds to a classical model of computation, a Lag system, that has long been known to be computationally universal. By leveraging a new proof, we show that a universal Turing machine can be simulated by a Lag system with 2027 production rules. We then investigate whether an existing large language model can simulate the behaviour of such a universal Lag system. We give an affirmative answer by showing that a single system-prompt can be developed for gemini-1.5-pro-001 that drives the model, under deterministic (greedy) decoding, to correctly apply each of the 2027 production rules. We conclude that, by the Church-Turing thesis, prompted gemini-1.5-pro-001 with extended autoregressive (greedy) decoding is a general purpose computer.