# Memory makes computation universal, remember?

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 56 references that are in the map.
- First posted on arXiv 23 Dec 2024.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality](https://mlsanity.com/paper/2405.21060/) (2024)
- [Mind Your Step (by Step): Chain-of-Thought can Reduce Performance on Tasks where Thinking Makes Humans Worse](https://mlsanity.com/paper/2410.21333/) (2024)
- [Were RNNs All We Needed?](https://mlsanity.com/paper/2410.01201/) (2024)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)
- [Recursive Chain-of-Feedback Prevents Performance Degradation from Redundant Prompting](https://mlsanity.com/paper/2402.02648/) (2024)
- [Memory Lower Bounds and Impossibility Results for Anonymous Dynamic Broadcast](https://mlsanity.com/paper/2407.09714/) (2024)
- [Overcoming Memory Constraints in Quantum Circuit Simulation with a High-Fidelity Compression Framework](https://mlsanity.com/paper/2410.14088/) (2024)

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

- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)
- [Reflection Pretraining Enables Token-Level Self-Correction in Biological Sequence Models](https://mlsanity.com/paper/2512.20954/) (2025)

## Abstract (arXiv)

Recent breakthroughs in AI capability have been attributed to increasingly sophisticated architectures and alignment techniques, but a simpler principle may explain these advances: memory makes computation universal. Memory enables universal computation through two fundamental capabilities: recursive state maintenance and reliable history access. We formally prove these requirements are both necessary and sufficient for universal computation. This principle manifests across scales, from cellular computation to neural networks to language models. Complex behavior emerges not from sophisticated processing units but from maintaining and accessing state across time. We demonstrate how parallel systems like neural networks achieve universal computation despite limitations in their basic units by maintaining state across iterations. This theoretical framework reveals a universal pattern: computational advances consistently emerge from enhanced abilities to maintain and access state rather than from more complex basic operations. Our analysis unifies understanding of computation across biological systems, artificial intelligence, and human cognition, reminding us that humanity's own computational capabilities have evolved in step with our technical ability to remember through oral traditions, writing, and now computing.