Differentiable Exact Learning of Algorithms

We introduce a framework for differentiable exact learning of algorithms. The framework couples a state-tracking neural controller to an unbounded external environment and trains on policy-trajectory observations (PTOs) -- traces that record the environment's evolution under an expert's actions without exposing the expert's internal state. This supervision regime sidesteps Gold's impossibility barrier for input-output recursive learning while avoiding the unrealistic internal-state access required by prior provably correct approaches. As controllers, we propose Differentiable Finite-State Transducers (DFSTs), a minimalist multilinear model family that contains no nonlinearities and admits log-parallel training via prefix scans. Trained on tiny datasets, DFST and RNN controllers achieve error-free generalization on binary and decimal addition and multiplication to operands thousands of times longer than the training examples. Moreover, we provide strong empirical proof for exact learning of universal computation. Finally, we develop an extraction procedure that recovers compact finite-state transducers from trained controllers. We prove under a geometric clustering assumption that for binary addition the extracted transducer exactly replicates the expert policy on all valid inputs -- certifying differentiable exact learning of the algorithm.