Differentiable learning of automata
2016-10-14 — 2025-06-05
Wherein the Training of Stack Machines and Random-Access Machines Is Undertaken via Differentiable Neural Formalisms, and Turing-Machine–like Controllers Are Induced From Data.
We learn stack machines, random access machines, nested hierarchical parsing machines, Turing machines, and whatever other automata-with-memory we want from data. In other words, we’re teaching computers to program themselves via a deep learning formalism.
This is an obvious idea — one of the original ideas from the GOFAI days. How to make it work in NNs isn’t obvious, but there are some charming toy examples. There are also arguably non-toy examples in the form of transformers which learn to parse and generate actual code.
Obviously, a hypothetical superhuman Artificial General Intelligence would be good at handling computer-science problems.
Directly learning automata isn’t the absolute hippest research area right now, though — it’s hard in general and also not very saleable. However, it’s simple enough, in some sense, to be analytically tractable. Some progress has been made. I feel that most of the hyped research that looks like differentiable computer learning sits in the slightly better-contained area of reinforcement learning where more progress can be made, or in the hot area of large LLMs which are harder to explain but solve the same kind of problems while looking different inside.
Related: grammatical inference, memory machines, computational complexity results in NNs, reasoning with LLMs. Automata are a kind of formalization of reasoning, but I think they’re more easily considered as their own thing. If we call this program synthesis, then these things sound connected. See learnable memory for a survey of the state of the art.
1 Programs as singularities
Murfet and Troiani (2025), citing (Clift and Murfet 2019, 2020; Clift, Murfet, and Wallbridge 2020; Ehrhard and Regnier 2003; Waring, n.d.) uses singular learning theory to study the geometry of the space of programs and how to learn them.
2 Differentiable Cellular Automata
3 Recursion on a latent
A small-model thread that belongs here more than with the language-model reasoners: HRM (G. Wang et al. 2025) and its stripped-down successor TRM (Jolicoeur-Martineau 2025) crack ARC-AGI, Sudoku and mazes with 7–27M-parameter nets that recurse on a fixed-size latent instead of emitting a long chain of thought. HRM’s headline was a brain-inspired two-timescale hierarchy, but ARC Prize’s ablation pinned the gains on the outer refine-and-retry loop plus heavy per-task augmentation rather than the hierarchy — and TRM then beat HRM with a plain two-layer net, which rather makes the case. This makes them siblings to the ARC-AGI Without Pretraining paper (Liao and Gu 2025). They are a cousin of test-time scaling — more compute per problem beats a bigger single shot — but transductive puzzle-solvers trained per task, learning an iterative computer rather than doing language. Whether recurse-on-a-latent crosses over to language is the open question.
4 Incoming
Latent space of small turing machines
Blazek claims his neural networks implement predicate logic directly and are tractable, which would be interesting to look into (Blazek and Lin 2021, 2020; Blazek, Venkatesh, and Lin 2021).
Google-branded: Differentiable Neural Computers.
Christopher Olah’s Characteristically pedagogic intro.
Adrian Colyer’s introduction to neural Turing machines.
Andrej Karpathy’s memory machine list.
Facebook’s GTN:
GTN is an open source framework for automatic differentiation with a powerful, expressive type of graph called weighted finite-state transducers (WFSTs). Just as PyTorch provides a framework for automatic differentiation with tensors, GTN provides such a framework for WFSTs. AI researchers and engineers can use GTN to more effectively train graph-based machine learning models.