---
title: "Memory Augmented Large Language Models are"
description: "Transformer language models can only attend to an input of bounded length, so a deterministic model… 23 references, cited by 10 papers here."
authors: ["Dale Schuurmans"]
year: 2023
venue: "arXiv:2301.04589"
source: "https://arxiv.org/abs/2301.04589"
doi: "10.48550/arxiv.2301.04589"
arxiv: "2301.04589"
licence: "CC BY 4.0 (arXiv)"
licence_url: "http://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/schuurmans-2023-memory-augmented-large-language-models/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/schuurmans-2023-memory-augmented-large-language-models/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/) / Memory Augmented Large Language Models are Computationally Universal

# Memory Augmented Large Language Models are Computationally Universal

**Authors:** [Dale Schuurmans](https://md.research.elamur.ai/free/en/authors/dale-schuurmans/) · **Year:** 2023 · **Venue:** arXiv:2301.04589 · **Licence:** [CC BY 4.0 (arXiv)](http://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://arxiv.org/abs/2301.04589) · [PDF](https://arxiv.org/pdf/2301.04589) · [DOI 10.48550/arxiv.2301.04589](https://doi.org/10.48550/arxiv.2301.04589) · [arXiv 2301.04589](https://arxiv.org/abs/2301.04589) · [OpenAlex](https://openalex.org/W4315882015)

**Citations:** 9 citations (OpenAlex, 2026-10-14) · [10](https://md.research.elamur.ai/free/en/papers/schuurmans-2023-memory-augmented-large-language-models/cited-by/) in our library, of the 149,439 papers whose bibliographies we read

## Summary

Transformer language models can only attend to an input of bounded length, so a deterministic model of this kind is formally no more powerful than a finite automaton. Schuurmans asks whether adding an external feedback loop fundamentally expands what such models can compute. He pairs a frozen Flan-U-PaLM 540B with an associative read-write memory, a key-value dictionary, in the style of a von Neumann stored-instruction computer. The language model acts as the CPU and the dictionary acts as RAM. Python regular expressions shuttle prompts and variable assignments between the two, and these parsers are restricted to finite-state operations so that the universality cannot come from the glue code. A dedicated "prompt program" then makes the system emulate the universal Turing machine U 15,2. Correctness reduces to confirming that the model answers each of a finite set of possible prompts correctly. No weights are changed and no training is involved. The work shows that existing LLMs are already Turing-universal when given unbounded external memory, which sets it apart from earlier proofs that relied on specially constructed network weights.

## Key points

- **Setup:** The model is Flan-U-PaLM 540B with frozen weights. The memory is a Python dictionary, and memory location `op` serves as the instruction register. The loop repeats until `op` contains `halt`.
- **Glue code:** All pre- and post-processing uses the Python `re` library and covers:
  - parsing assignments,
  - splicing in values with `@[...]` and `%[...]`,
  - integer `+=` and `-=` updates.
  
  Nested substitution is capped at depth 2 so that every step stays finite-state.
- **Target machine:** The system simulates U 15,2 (Neary & Woods), using one terse prompt for each machine state, labelled A through O. The proof is a finite series of verification tests, one for each combination of state and symbol read.
- **Brittleness:** Prompts had to be compact and carefully engineered, and not every LLM tried succeeded. The model handled if-then conditionals reliably but not if-then-else, which made the smaller U 6,4 impractical to simulate.
- **Alternatives and analogies:** An earlier version used Rule 110. It was dropped because it needs an unbounded periodic initialization, while U 15,2 needs only a bounded one. The author compares the prompt language to early assembly languages.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of Alberta](https://md.research.elamur.ai/free/en/universities/university-of-alberta/) — University, Edmonton, Canada · 44 works · 3,236 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

🧭 Topics (1): [🧠 Language models & pretraining](https://md.research.elamur.ai/free/en/topics/language-models/) · 3,320 works

## Cite

Cite as: Dale Schuurmans. 2023. Memory Augmented Large Language Models are Computationally Universal. arXiv:2301.04589.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@misc{schuurmans2023memory,
  title = {{Memory Augmented Large Language Models are Computationally Universal}},
  author = {Dale Schuurmans},
  year = {2023},
  doi = {10.48550/arxiv.2301.04589},
  eprint = {2301.04589},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2301.04589}
}
```

- [← previous Infusing Hierarchical Guidance into Prompt Tuning: A Parameter-Efficient Framework for Multi-level Implicit Discourse Relation Recognition](https://md.research.elamur.ai/free/en/papers/zhao-2023-infusing-hierarchical-guidance-into-prompt/)
- [next → MPSA-DenseNet: A novel deep learning model for English accent classification](https://md.research.elamur.ai/free/en/papers/song-2023-mpsa-densenet-novel-deep-learning/)
- [↑ back to papers of 2023](https://md.research.elamur.ai/free/en/papers/2023/page/10/)

## References

23 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Bhattamishra, S., Patel, A., and Goyal, N. (2020). On the computational power of Transformers and its implications in sequence modeling. In Conference on Computational Natural Language Learning (CONLL). [find](https://scholar.google.com/scholar?q=Bhattamishra%2C+S%2E%2C+Patel%2C+A%2E%2C+and+Goyal%2C+N%2E+%282020%29%2E+On+the+computational+power+of+Transformers+and+its+implications+in+sequence+modeling%2E+In+Conference+on+Computational+Natural+Language+Learning+%28CONLL)
2. Böhm, C. (1954). Calculatrices digitales du déchiffrage de formules logico-mathématiques par la machine même dans la conception du programme. PhD thesis, ETH Zürich. [find](https://scholar.google.com/scholar?q=Bo%CC%88hm%2C+C%2E+%281954%29%2E+Calculatrices+digitales+du+de%CC%81chiffrage+de+formules+logico%2Dmathe%CC%81matiques+par+la+machine+me%CC%82me+dans+la+conception+du+programme%2E+PhD+thesis%2C+ETH+Zu%CC%88rich%2E)
3. Booth, A. and Britten, K. (1947). General considerations in the deisgn of an all purpose electronic digital computer. Technical report, Institute for Advanced Study, Princeton. 2nd ed. [find](https://scholar.google.com/scholar?q=Booth%2C+A%2E+and+Britten%2C+K%2E+%281947%29%2E+General+considerations+in+the+deisgn+of+an+all+purpose+electronic+digital+computer%2E+Technical+report%2C+Institute+for+Advanced+Study%2C+Princeton%2E+2nd+ed%2E)
4. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B… — [Language Models are Few-Shot Learners](https://md.research.elamur.ai/free/en/papers/brown-2020-language-models-few-shot-learners/)
5. Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., Webson, A., Gu, S. S., Dai, Z., Suzgun, M., Chen, X., Chowdhery, A., Castro-Ros, A., Pellat, M., Robinson, K., Valter, D., Narang, S., Mishra, G., Yu, A., Zhao, V., Huang, Y., Dai, A., Yu, H… [find](https://scholar.google.com/scholar?q=Chung%2C+H%2E+W%2E%2C+Hou%2C+L%2E%2C+Longpre%2C+S%2E%2C+Zoph%2C+B%2E%2C+Tay%2C+Y%2E%2C+Fedus%2C+W%2E%2C+Li%2C+Y%2E%2C+Wang%2C+X%2E%2C+Dehghani%2C+M%2E%2C+Brahma%2C+S%2E%2C+Webson%2C+A%2E%2C+Gu%2C+S%2E+S%2E%2C+Dai%2C+Z%2E%2C+Suzgun%2C+M%2E%2C+Chen%2C+X%2E%2C+Chowdhery%2C+A%2E%2C+Castro%2DRos%2C+A%2E%2C+Pella)
6. Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15:1–40. [find](https://scholar.google.com/scholar?q=Cook%2C+M%2E+%282004%29%2E+Universality+in+elementary+cellular+automata%2E+Complex+Systems%2C+15%3A1%E2%80%9340%2E)
7. Dohan, D., Xu, W., Lewkowycz, A., Austin, J., Bieber, D., Lopes, R. G., Wu, Y., Michalewski, H., Saurous, R. A., Sohl-dickstein, J., Murphy, K., and Sutton, C. (2022). Language model cascades. arXiv 2207.10342. [find](https://scholar.google.com/scholar?q=Dohan%2C+D%2E%2C+Xu%2C+W%2E%2C+Lewkowycz%2C+A%2E%2C+Austin%2C+J%2E%2C+Bieber%2C+D%2E%2C+Lopes%2C+R%2E+G%2E%2C+Wu%2C+Y%2E%2C+Michalewski%2C+H%2E%2C+Saurous%2C+R%2E+A%2E%2C+Sohl%2Ddickstein%2C+J%2E%2C+Murphy%2C+K%2E%2C+and+Sutton%2C+C%2E+%282022%29%2E+Language+model+cascades%2E+arXiv+2)
8. Neary, T. (2008). Small universal Turing machines. PhD thesis, National University of Ireland, Maynooth. [find](https://scholar.google.com/scholar?q=Neary%2C+T%2E+%282008%29%2E+Small+universal+Turing+machines%2E+PhD+thesis%2C+National+University+of+Ireland%2C+Maynooth%2E)
9. Neary, T. and Woods, D. (2009). Four small universal Turing machines. Fundamenta Informaticae, 91:105–126. [find](https://scholar.google.com/scholar?q=Neary%2C+T%2E+and+Woods%2C+D%2E+%282009%29%2E+Four+small+universal+Turing+machines%2E+Fundamenta+Informaticae%2C+91%3A105%E2%80%93126%2E)
10. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. (2022). [Training language models to follow instruction…](https://md.research.elamur.ai/free/en/papers/ouyang-2022-training-language-models-follow-instructions/)
11. Pérez, J., Marinković, J., and Parceló, P. (2019). On the Turing completeness of modern neural network architectures. In International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=Pe%CC%81rez%2C+J%2E%2C+Marinkovic%CC%81%2C+J%2E%2C+and+Parcelo%CC%81%2C+P%2E+%282019%29%2E+On+the+Turing+completeness+of+modern+neural+network+architectures%2E+In+International+Conference+on+Learning+Representations+%28ICLR%29%2E)
12. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners. [find](https://scholar.google.com/scholar?q=Radford%2C+A%2E%2C+Wu%2C+J%2E%2C+Child%2C+R%2E%2C+Luan%2C+D%2E%2C+Amodei%2C+D%2E%2C+and+Sutskever%2C+I%2E+%282019%29%2E+Language+models+are+unsupervised+multitask+learners%2E)
13. Schulman, J., Zoph, B., Kim, C., Hilton, J., Menick, J., Weng, J., Uribe, J. F. C., Fedus, L., Metz, L., Pokorny, M., Lopes, R. G., Zhao, S., Vijayvergiya, A., Sigler, E., Perelman, A., Voss, C., Heaton, M., Parish, J., Cummings, D., Nayak, R., Balcom, V., Schnurr, D., Kaftan, T., Hallacy, C., Turle… [find](https://scholar.google.com/scholar?q=Schulman%2C+J%2E%2C+Zoph%2C+B%2E%2C+Kim%2C+C%2E%2C+Hilton%2C+J%2E%2C+Menick%2C+J%2E%2C+Weng%2C+J%2E%2C+Uribe%2C+J%2E+F%2E+C%2E%2C+Fedus%2C+L%2E%2C+Metz%2C+L%2E%2C+Pokorny%2C+M%2E%2C+Lopes%2C+R%2E+G%2E%2C+Zhao%2C+S%2E%2C+Vijayvergiya%2C+A%2E%2C+Sigler%2C+E%2E%2C+Perelman%2C+A%2E%2C+Voss%2C+C%2E%2C+Heat)
14. Shannon, C. (1956). A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies, 34:157–165. [find](https://scholar.google.com/scholar?q=Shannon%2C+C%2E+%281956%29%2E+A+universal+Turing+machine+with+two+internal+states%2E+Automata+Studies%2C+Annals+of+Mathematics+Studies%2C+34%3A157%E2%80%93165%2E)
15. Siegelmann, H. and Sontag, E. (2019). On the computational power of neural nets. In Conference on Learning Theory (COLT). [find](https://scholar.google.com/scholar?q=Siegelmann%2C+H%2E+and+Sontag%2C+E%2E+%282019%29%2E+On+the+computational+power+of+neural+nets%2E+In+Conference+on+Learning+Theory+%28COLT%29%2E)
16. Sipser, M. (2013). Introduction to the Theory of Computation. Cengage Learning, 3rd edition. [find](https://scholar.google.com/scholar?q=Sipser%2C+M%2E+%282013%29%2E+Introduction+to+the+Theory+of+Computation%2E+Cengage+Learning%2C+3rd+edition%2E)
17. Turing, A. (1937). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42:230–265. [find](https://scholar.google.com/scholar?q=Turing%2C+A%2E+%281937%29%2E+On+computable+numbers%2C+with+an+application+to+the+Entscheidungsproblem%2E+Proceedings+of+the+London+Mathematical+Society%2C+2%2C+42%3A230%E2%80%93265%2E)
18. von Neumann, J. (1945). First draft of a report on the EDVAC. [find](https://scholar.google.com/scholar?q=von+Neumann%2C+J%2E+%281945%29%2E+First+draft+of+a+report+on+the+EDVAC%2E)
19. Wei, C., Chen, Y., and Ma, T. (2022a). Statistically meaningful approximation: a case study on approximating Turing machines with Transformers. In Advances in Neural Information Processing Systems (NeurIPS). [find](https://scholar.google.com/scholar?q=Wei%2C+C%2E%2C+Chen%2C+Y%2E%2C+and+Ma%2C+T%2E+%282022a%29%2E+Statistically+meaningful+approximation%3A+a+case+study+on+approximating+Turing+machines+with+Transformers%2E+In+Advances+in+Neural+Information+Processing+Systems+%28Ne)
20. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., and Zhou, D. (2022b). [Chain of thought prompting elicits reasoning in large language models](https://md.research.elamur.ai/free/en/papers/wei-2022-chain-thought-prompting-elicits-reasoning/). In Advances in Neural Information Processing Systems (NeurIPS).
21. Weiss, G., Goldberg, Y., and Yahav, E. (2018). [On the practical computational power of finite precision RNNs for language recognition](https://md.research.elamur.ai/free/en/papers/weiss-2018-practical-computational-power-finite-precision/). In Conference of the Association for Computational Linguistics (ACL).
22. Wolfram, S. (2002). A New Kind of Science. Wolfram Media. [find](https://scholar.google.com/scholar?q=Wolfram%2C+S%2E+%282002%29%2E+A+New+Kind+of+Science%2E+Wolfram+Media%2E)
23. Zhou, D., Schärli, N., How, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q., and Chi, E. (2022). [Least-to-most prompting enables complex reasoning in large language models](https://md.research.elamur.ai/free/en/papers/al-2022-least-most-prompting-enables-complex/). arXiv 2205.10625.

*Updated 30 October 2026*