Pith. sign in

REVIEW 4 cited by

Memory Augmented Large Language Models are Computationally Universal

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2301.04589 v1 pith:SKFNARGP submitted 2023-01-10 cs.CL cs.FL

Dale Schuurmans This is my paper · ORCID
classification cs.CLcs.FL
keywords languagelargememorycomputationallymodelmodelsuniversalaugmented
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

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, $U_{15,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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Planning with Transformers: Chain of Computation and Structured Context Windows

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Small transformers, trained from scratch on curated instruction traces and run inside a pointer-memory loop, solve BlocksWorld/Pancake at >99.89% and Tower of Hanoi to 20 disks.

  2. Position: Modular Memory is the Key to Continual Learning Agents

    cs.LG 2026-03 conditional novelty 6.0 of 10

    A modular memory combining in-context learning and in-weight learning is proposed as the key to continual learning agents.

  3. Code Simulation as a Proxy for High-order Tasks in Large Language Models

    cs.LG 2025-02 conditional novelty 5.0 of 10

    LLM performance on naturalistic reasoning tasks tracks performance on equivalent Python code simulation, but the effect is partly driven by pattern matching and memorization rather than faithful execution.

  4. Loki's Dance of Illusions: A Comprehensive Survey of Hallucination in Large Language Models

    cs.CL 2025-06 reject novelty 3.0 of 10

    A survey of LLM hallucination research that formalizes hallucination types and argues, via incompleteness and undecidability arguments, that hallucinations cannot be fully eliminated.

Pith tools