mlsanityData to 7 Oct 2026

Memory Augmented Large Language Models are Computationally Universal

arXiv 2301.04589 ↗First posted 10 Jan 2023cs.CL cs.FLcited by 45

Not on the map. Why?

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.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). Builds on 10 of its 24 references that are in the map. First posted on arXiv 10 Jan 2023.

Builds on

10 of 24 references.

References · 10

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2022Training language models to follow instructions with human feedbackcited by 15,712
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,302
  4. 2022Scaling Instruction-Finetuned Language Modelscited by 2,997
  5. 2022Least-to-Most Prompting Enables Complex Reasoning in Large Language Modelscited by 1,397
  6. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  7. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  8. 2022Language Model Cascadescited by 104
  9. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  10. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 17; 2024: 10; 2025: 10; 2026: 8.

45 papers.

Sort:

By area:

  1. 2023A Survey on Large Language Model based Autonomous Agentscited by 2,203
  2. 2023A Comprehensive Overview of Large Language Modelscited by 639
  3. 2023Language Models can Solve Computer Taskscited by 371
  4. 2023Foundation Models for Decision Making: Problems, Methods, and Opportunitiescited by 160
  5. 2023ChatDB: Augmenting LLMs with Databases as Their Symbolic Memorycited by 136
  6. 2023Domain Specialization as the Key to Make Large Language Models Disruptive: A Comprehensive Surveycited by 134
  7. 2024LLMs Will Always Hallucinate, and We Need to Live With Thiscited by 77
  8. 2023Suspicion-Agent: Playing Imperfect Information Games with Theory of Mind Aware GPT-4cited by 67
  9. 2023LLM Censorship: A Machine Learning Challenge or a Computer Security Problem?cited by 47
  10. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 47
  11. 2023Large Language Models Are Semi-Parametric Reinforcement Learning Agentscited by 42
  12. 2023How Powerful are Decoder-Only Transformer Neural Models?cited by 20
33 more
  1. 2023GPT is becoming a Turing machine: Here are some ways to program itcited by 16
  2. 2024Code Simulation Challenges for Large Language Modelscited by 15
  3. 2024Autoregressive Large Language Models are Computationally Universalcited by 14
  4. 2023Analysis of ChatGPT on Source Codecited by 12
  5. 2023Large Language Model Programscited by 11
  6. 2023Generative AI vs. AGI: The Cognitive Strengths and Weaknesses of Modern LLMscited by 11
  7. 2024Professional Agents -- Evolving Large Language Models into Autonomous Experts with Human-Level Competenciescited by 9
  8. 2025AI Agents as Universal Task Solverscited by 9
  9. 2024From Text to Life: On the Reciprocal Relationship between Artificial Life and Large Language Modelscited by 8
  10. 2025MOOM: Maintenance, Organization and Optimization of Memory in Ultra-Long Role-Playing Dialoguescited by 8
  11. 2026Position: Modular Memory is the Key to Continual Learning Agentscited by 7
  12. 2025Code Simulation as a Proxy for High-order Tasks in Large Language Modelscited by 6
  13. 2025Understanding Prompt Tuning and In-Context Learning via Meta-Learningcited by 6
  14. 2025Loki's Dance of Illusions: A Comprehensive Survey of Hallucination in Large Language Modelscited by 6
  15. 2025Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformerscited by 6
  16. 2025EvoMem: Improving Multi-Agent Planning with Dual-Evolving Memorycited by 6
  17. 2024Can Language Models Pretend Solvers? Logic Code Simulation with LLMscited by 4
  18. 2024Enhancing Long Context Performance in LLMs Through Inner Loop Query Mechanismcited by 4
  19. 2025Distributed Multi-Agent Coordination Using Multi-Modal Foundation Modelscited by 3
  20. 2024FragRel: Exploiting Fragment-level Relations in the External Memory of Large Language Modelscited by 1
  21. 2024Large Language Models and the Extended Church-Turing Thesiscited by 1
  22. 2024METEOR: Evolutionary Journey of Large Language Models from Guidance to Self-Growthcited by 1
  23. 2026Universal computation is intrinsic to language model decodingcited by 1
  24. 2026The Library Theorem: How External Organization Governs Agentic Reasoning Capacitycited by 1
  25. 2023Applying Standards to Advance Upstream & Downstream Ethics in Large Language Modelscited by 0
  26. 2023Model of models -- Part 1cited by 0
  27. 2025Towards Understanding Multi-Round Large Language Model Reasoning: Approximability, Learnability and Generalizabilitycited by 0
  28. 2025Lessons from Neuroscience for AI: How integrating Actions, Compositional Structure and Episodic Memory could enable Safe, Interpretable and Human-Like AIcited by 0
  29. 2026Neural Paging: Learning Context Management Policies for Turing-Complete Agentscited by 0
  30. 2026Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Managementcited by 0
  31. 2026HyperPatch: Sequential Knowledge Editing Under n-ary Structural Driftcited by 0
  32. 2026Planning with Transformers: Chain of Computation and Structured Context Windowscited by 0
  33. 2026BRACE: Differential Privacy for Dense Associative Memory with LSR Energycited by 0