# Memory Augmented Large Language Models are Computationally Universal

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 10 Jan 2023.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [On the Practical Computational Power of Finite Precision RNNs for Language Recognition](https://mlsanity.com/paper/1805.04908/) (2018)
- [Language Model Cascades](https://mlsanity.com/paper/2207.10342/) (2022)
- [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)

## Built on by (most cited first, 30 of 47)

- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [A Comprehensive Overview of Large Language Models](https://mlsanity.com/paper/2307.06435/) (2023)
- [Language Models can Solve Computer Tasks](https://mlsanity.com/paper/2303.17491/) (2023)
- [Foundation Models for Decision Making: Problems, Methods, and Opportunities](https://mlsanity.com/paper/2303.04129/) (2023)
- [ChatDB: Augmenting LLMs with Databases as Their Symbolic Memory](https://mlsanity.com/paper/2306.03901/) (2023)
- [Domain Specialization as the Key to Make Large Language Models Disruptive: A Comprehensive Survey](https://mlsanity.com/paper/2305.18703/) (2023)
- [LLMs Will Always Hallucinate, and We Need to Live With This](https://mlsanity.com/paper/2409.05746/) (2024)
- [Suspicion-Agent: Playing Imperfect Information Games with Theory of Mind Aware GPT-4](https://mlsanity.com/paper/2309.17277/) (2023)
- [The Expressive Power of Transformers with Chain of Thought](https://mlsanity.com/paper/2310.07923/) (2023)
- [LLM Censorship: A Machine Learning Challenge or a Computer Security Problem?](https://mlsanity.com/paper/2307.10719/) (2023)
- [Large Language Models Are Semi-Parametric Reinforcement Learning Agents](https://mlsanity.com/paper/2306.07929/) (2023)
- [How Powerful are Decoder-Only Transformer Neural Models?](https://mlsanity.com/paper/2305.17026/) (2023)
- [GPT is becoming a Turing machine: Here are some ways to program it](https://mlsanity.com/paper/2303.14310/) (2023)
- [Code Simulation Challenges for Large Language Models](https://mlsanity.com/paper/2401.09074/) (2024)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)
- [Analysis of ChatGPT on Source Code](https://mlsanity.com/paper/2306.00597/) (2023)
- [Large Language Model Programs](https://mlsanity.com/paper/2305.05364/) (2023)
- [Generative AI vs. AGI: The Cognitive Strengths and Weaknesses of Modern LLMs](https://mlsanity.com/paper/2309.10371/) (2023)
- [Professional Agents -- Evolving Large Language Models into Autonomous Experts with Human-Level Competencies](https://mlsanity.com/paper/2402.03628/) (2024)
- [AI Agents as Universal Task Solvers](https://mlsanity.com/paper/2510.12066/) (2025)
- [From Text to Life: On the Reciprocal Relationship between Artificial Life and Large Language Models](https://mlsanity.com/paper/2407.09502/) (2024)
- [MOOM: Maintenance, Organization and Optimization of Memory in Ultra-Long Role-Playing Dialogues](https://mlsanity.com/paper/2509.11860/) (2025)
- [Position: Modular Memory is the Key to Continual Learning Agents](https://mlsanity.com/paper/2603.01761/) (2026)
- [Code Simulation as a Proxy for High-order Tasks in Large Language Models](https://mlsanity.com/paper/2502.03568/) (2025)
- [Loki's Dance of Illusions: A Comprehensive Survey of Hallucination in Large Language Models](https://mlsanity.com/paper/2507.02870/) (2025)
- [Understanding Prompt Tuning and In-Context Learning via Meta-Learning](https://mlsanity.com/paper/2505.17010/) (2025)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [EvoMem: Improving Multi-Agent Planning with Dual-Evolving Memory](https://mlsanity.com/paper/2511.01912/) (2025)
- [Can Language Models Pretend Solvers? Logic Code Simulation with LLMs](https://mlsanity.com/paper/2403.16097/) (2024)
- [Enhancing Long Context Performance in LLMs Through Inner Loop Query Mechanism](https://mlsanity.com/paper/2410.12859/) (2024)

## Abstract (arXiv)

We show that transformer-based large language models are computationally universal when augmented with an external memory. Any deterministic language model that conditions on strings of bounded length is equivalent to a finite automaton, hence computationally limited. However, augmenting such models with a read-write memory creates the possibility of processing arbitrarily large inputs and, potentially, simulating any algorithm. We establish that an existing large language model, Flan-U-PaLM 540B, can be combined with an associative read-write memory to exactly simulate the execution of a universal Turing machine, U15,2. A key aspect of the finding is that it does not require any modification of the language model weights. Instead, the construction relies solely on designing a form of stored instruction computer that can subsequently be programmed with a specific set of prompts.