Learning to Program Turing Machines: From Nondeterministic to Deterministic Programs

Recent results on reasoning with large language models show that autoregressive transformers are general-purpose machines that can be programmed via input prompts. The difficulty of verifying the correctness of such programs prompted us to investigate a different line of work. Instead of relying on an emergent machine, we design a general-purpose machine and learn programs for it that encode solutions to challenging problems through search. We hypothesize that searching in the space of nondeterministic programs to find deterministic ones can improve our system’s ability to discover algorithmic solutions efficiently from small amounts of data. We introduce a learning system that starts with nondeterministic programs, represented by a learned policy over the machine’s operators, and transitions to a deterministic program once learning is complete. We can then verify the resulting deterministic program for correctness. Experiments on challenging problems, including bit addition and bit multiplication, show that we can discover efficient and correct programs from only hundreds of input-output examples. Our results also show that searching in the space of nondeterministic programs is substantially more efficient than a baseline that searches directly in the space of deterministic programs, thus supporting our hypothesis. Compared to the Neural Turing Machines line of work (Graves et al., 2014), we can discover algorithms using over 200 times less data than existing approaches.