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.
University of Tubingen, Tubingen, Germany · Center for Cognitive Science, Technical University Darmstadt, Darmstadt, Germany · 3Hessian.AI, Darmstadt, Germany +1