A neural controller trained only on expert action traces can be proven to run algorithms exactly: a 4,335-parameter DFST clears all 10 universal-simulation tasks at the 500-symbol cap
Synopsis
A differentiable exact-learning framework couples a state-tracking neural controller to an unbounded external grid environment and trains it only on policy-trajectory observations, which record expert observations and actions while hiding internal states. A 4,335-parameter DFST trained on just 75 traces with inputs of at most 5 symbols reaches the 500-symbol evaluation cap on all 10 universal-simulation tasks, 5 of them held out, and discrete controllers extracted from trained models are proven equivalent to the expert universal interpreter.
Interpretation
A neural controller can now be trained to execute algorithms on arbitrarily long inputs while seeing only expert actions, never expert internal states, and a provably correct discrete controller can be extracted from the trained model afterward. Transformers and RNNs trained on input-output pairs for arithmetic previously generalized only marginally to longer inputs, while neural programmer-interpreters that provably recover decimal addition rely on recursive call and return annotations, supervision stronger than merely observing expert actions in an external environment. On binary and decimal addition and multiplication, DFSTs trained on traces with operands of at most 3 digits for addition and 5 for multiplication reach testing caps of 5000 digits per operand for addition and 1000 for multiplication, passing both random probes and structured repdigit probes such as all-9 and all-1 inputs.
The recipe places a neural controller capable of simulating finite-state machines inside a symbolic grid that grows as needed; at each step the controller reads the symbol under its cell and emits a symbol to write plus a motion direction. The training signal is policy-trajectory observations, which record how the environment evolves under the expert policy without exposing the expert's internal state transitions, sidestepping the barrier that input-output supervision alone cannot identify every computable function in the limit. On universal simulation, a 15-dimensional DFST with 4,335 parameters trained on 75 traces from 5 programs with inputs of at most 5 symbols reaches the 500-symbol cap on all 10 tasks, including 5 held-out programs; the longest sampled trajectory requires 15,316,822 consecutive expert-action matches.
A trained model yields a finite discrete state machine by clustering hidden states or by sharpening Softmax transition probabilities, and the correctness proof is then carried out on that discrete object. Finite-length testing cannot by itself prove correctness on arbitrary inputs, because no computable finite testing horizon guarantees that two grid agents agree on all inputs. Eight certificates cover binary and decimal addition, multiplication and universal simulation; the universal controllers are proven to correctly simulate every binary Turing machine on every nonempty binary input, while transferring the conclusion to the neural controllers themselves requires graph-stability or bounded-leakage assumptions.
Perspective
The demonstrated scope is binary and decimal addition and multiplication on a symbolic grid, plus a 15-state universal Turing-machine simulator; evaluation uses capped searches of 5000 digits for addition, 1000 for multiplication and 500 symbols for universal simulation, with universal training inputs of at most 5 symbols. The intended reader is a machine-learning researcher interested in algorithmic extrapolation and formal verification.
Transferring the extracted controllers' equivalence to the neural controllers requires graph-stability or bounded-leakage assumptions that are empirically supported rather than proven. Softmax DFSTs fail to fit even small training sets on decimal tasks, and ordinary-DFST success varies across training schedules, with additional updates not necessarily improving generalization.
