Teaching a Minimalist Machine to Discover Recursive Programs for Arithmetic
Authors: Dominik Magiera, Christiane Wiebel-Herboth, Frank Jäkel
Organizations: Centre for Cognitive Science & Institute of Psychology, Technische Universität Darmstadt, Germany · Honda Research Institute Europe GmbH, Offenbach am Main, Germany
Humans can often acquire and synthesize complex, recursive concepts from minimal experience. Leveraging cognitive insights, we propose the Minimalist Machine, a framework for inductive program synthesis designed to model such conceptual learning. The system uses a compact relational subset of Prolog: Programs are searched within a fixed schema of body-free facts and two-body conjunctive Horn clauses. Recursion is not defined by a dedicated metarule. Instead, it emerges when a target predicate is reused inside the body of a learned clause. Inspired by a primary school curriculum, the model is taught through a human-curated, sequential introduction of new concepts in arithmetic. Starting from initially empty knowledge base, it first acquires simple structural predicates, then successor-based state transformations, and finally recursive programs for addition, subtraction, multiplication, and division. Ultimately, this approach yields the fully transparent, inductive reasoning trace necessary for human-like conceptual learning.
Figures & tables
Type
Schema
Fact
p.
p((X,Y)).
p(((X,Y),Y)).
p(((Y,X),Y)).
Rule
p((X,Y)):-p0((V0,V1)),p1((V2,V3)).
Table 1: Minimal set of candidate clause schemas. For facts, X and Y may remain variables or be replaced by known symbols from B . For rules, V0,V1,V2,V3 denote body-argument positions, each ranging over {X,Y,Z} . The body predicates satisfy p0,p1∈B∪{p} , where B is the current set of known unary predicates available as background knowledge.
Figure 1: (a) Possible rectangle-game scenarios from the teaching game [ 18 ] . (b) Order of learned concepts for counting. (c) Examples for learning addition.
Figure 2: A human-inspired curriculum for basic arithmetic. The curriculum begins with structural fundamentals (1–3), then introduces counting and state-based addition and subtraction (4–7), and finally extends the same relational structure to container-and-remainder reasoning for multiplication and division (8–11). Child images created with GPT-5.5.
Figure 3: Learning multiplication as recursive container regrouping. The learned program opens one container at a time, adds its size to the remainder, and stops when the container count reaches zero. The advance predicate mult hides the explicit remainder state while preserving the learned recursive structure.
Figure 4: Iterations required for discovering the correct rule. The number of candidate clauses tested before the machine finds a rule consistent with the examples at each curriculum step.
Figure 5: Learned normalized rule patterns. The learned rule predicates are shown in a shared relational format, illustrating how the same two-body Horn-clause schema expresses projections, state transitions, recursion, and inverse mappings.
How do people build abstract, reusable knowledge from sequential experience under bounded cognitive resources? To answer this question, we integrate rate-distortion theory with recent advances in program induction to describe how prior knowledge shapes which future structures are cheap to encode and easy to discover. We formalize this in a hierarchical Adaptor Grammar (HAG) with distinct local (within-task) and global (across-task) libraries, governed jointly by constraints on memory and computation. In simulations, HAG achieves better rate-distortion trade-offs and stronger generalization than fixed grammars or shallow chunking methods. In an online melodic sequence-learning experiment, participants' recall errors reflected systematic simplifications and reaction times increased at inferred program boundaries. Trial-by-trial fits further showed that hierarchical libraries best explained individual differences in both recall and out-of-sample continuation choices, outperforming all alternative models. These findings cast structured learning as bounded program induction in which the order of experience shapes future abstractions a learner builds.
Hanqi Zhou, David G. Nagy, Peter Dayan +1
University of Tubingen, Tubingen, Germany · Center for Cognitive Science, Technical University Darmstadt, Darmstadt, Germany · 3Hessian.AI, Darmstadt, Germany +1
How humans grow and maintain abstract knowledge from the sparse, streaming noisy data of experience is a longstanding challenge in cognitive science. Any computational account must satisfy at least three desiderata: It must be (1) data-efficient and compute-efficient, (2) capture gradations of uncertainty to support intelligent inquiry and information gathering, and (3) be flexible enough to mentally represent the endless range of concepts people can learn and think about. Here we introduce a computational model that captures these three properties, by encoding symbolic knowledge as mental programs that combine natural language with source code, and sequentially inferring mental programs using LLM-guided Bayesian learning algorithms. Across a range of behavioral studies this model successfully reproduces quantitative signatures of human inductive learning and active inquiry, such as anchoring, garden-pathing, and other effects. In contrast, pure LLMs and classic Bayesian models either fail at the underlying task, or do not reproduce human behavior, or succeed only at exorbitant computational cost. These results suggest that one way humans continually grow their knowledge is by mentally representing many hypotheses spanning language-like and program-like representations, then revising those hypotheses to approximate Bayesian updates, while a bottom-up neural mechanism (an LLM) makes inference both tractable and learnable.
Wasu Top Piriyakulkij, Sam Acquaviva, Cassidy Langenfeld +2
1Cornell University · 2Massachusetts Institute of Technology
Humans can learn and generalize novel concepts from sparse data because they express knowledge in rich structural formats. In this paper, we propose that programs are a strong candidate for universal representation of concepts. We review computational models of concept learning that use programs as their concept representation and evaluate their contribution toward a universal representational language.