acceptodds
Under review as a conference paper at ICLR 2027

Learning to Program Turing Machines: From Nondeterministic to Deterministic Programs

Abstract

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.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Policy Guided Search, Algorithmic Reasoning, Neural Turing Machines, Program Induction

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_mcymOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper combines policy-guided search with an explicit Turing-like machine to discover deterministic programs from input–output examples. It learns formally verified programs for string manipulation and binary arithmetic from hundreds of examples, though harder tasks require tailored curricula and operations.

Critical strengths
  1. The method returns deterministic programs rather than computations encoded implicitly in neural weights. The paper reports machine-checked Lean 4 correctness proofs, providing stronger evidence of generalization than testing on longer inputs alone.

  2. The method discovers arithmetic programs using only hundreds of input–output examples, without requiring execution-trace supervision. This demonstrates a promising way to combine guided search with learning for algorithm discovery.

Critical weaknesses
  1. The broad idea of combining learned decision-making with explicit Turing-machine-style computation is already established. For example, Lai et al. (2024), Executing Arithmetic, learn arithmetic execution through explicit machine states and transitions and support composition of learned operators. The submitted paper (this paper) differs by discovering deterministic programs from input–output examples rather than learning to execute predefined algorithms. However, this distinction needs clearer positioning, and combining an explicit machine, policy-guided search, and supervised learning from successful traces does not by itself establish a substantial methodological advance. The paper would benefit from identifying precisely which part of its program-discovery procedure is novel and demonstrating its contribution through targeted ablations.

  2. The baseline comparison does not isolate the claimed advantage of nondeterministic search. The main baseline is a non-learning beam hill-climbing procedure over complete deterministic program tables, whereas the proposed method combines learned guidance, incremental table construction, a curriculum. These differences confound the central claim that searching nondeterministic traces is inherently more efficient than searching deterministic programs. A stronger evaluation should include deterministic search with comparable learned guidance, curriculum, and scoring, together with an ablation removing policy learning from the proposed procedure. The historical Neural GPU comparison also measures dataset size under substantially different inductive biases and supervision, so the “200× less data” result alone provides limited evidence of overall superiority.

Lai, Junyu, et al. "Executing arithmetic: Fine-tuning large language models as turing machines." arXiv preprint arXiv:2410.07896 (2024).

Questions for authors

Please refer to my weaknesses.

1 comment

Thank you for the detailed review and suggestions. We are glad you find the generalization results important and the method promising. We provide our response to both of the weaknesses below.

Positioning. We agree that combining learned components with explicit Turing machine computation is already established (Lai et al., 2024). However, we consider a much more challenging setting than Lai et al. Namely, we consider the discovery setting, where the underlying algorithm must be inferred from I/O examples. Lai et al. considered the strong supervision setting, where the model is given the computational traces of the algorithm it needs to learn. Learning to execute an algorithm from the algorithm's execution data is much easier than discovering the underlying algorithm from I/O examples. Our specific contribution is searching over nondeterministic execution traces and building the deterministic table incrementally, rather than searching over complete tables. We have not claimed novelty for policy-guided search or for learning from successful traces individually.

Isolating the contribution. It is true that no individual component is a unique contribution – it is the combination of all these components that gives us these results. We therefore appreciate the request for ablations, which show the impact of each individual methodological choice. Following your suggestion, we added the following ablations to the revised version of our paper:

  • We study the impact of nondeterminism as the reviewer requested, with a version of our deterministic baseline that uses learning (Section 5.4): we initialize the program tables based on the policy probabilities, which are trained across restarts, and then we run the same exhaustive beam search. This makes the learnt policy act as a deterministic program generator. The results show that this type of search performs better than the original beam search baseline, but not as well as our nondeterministic policy-based method, suggesting a difference between deterministic and nondeterministic search.
  • We also remove learning from our method, as suggested, keeping everything the same but never training the policy (Section 5.4) – without learning there is no gradient to guide the search through the large space of program traces.
  • Consistency through a shared table representation (Appendix I) – without it the policy does not solve any problems at all.
  • Round robin rollout (Appendix I) – without it we learn programs that heavily overfit to whichever problem instance is being used in the rollout, and the resulting program has no hope of being generalizable.
  • Verification step (Appendix I) – without it we see more early stopping, where a program solves all training instances but does not generalize on test data.
  • Context model observation (Appendix I) – for multiplication we observe similar performance even if we reduce the richness of the observation contexts, but for addition there is a drop in performance, indicating that there is value in using more detailed observations as input for the context model policy.

In summary, much of the generalization gain is from the shared table representation and the round-robin rollouts, while each of the other components contributes significantly to the correctness of the final programs.

Neural GPU comparison. We agree that this comparison involves different inductive biases and supervision. We revise our claim in Section 5.3 to be: “While we use different inductive biases given by the choice of the machine, and thus cannot conclude overall superiority over the Neural GPU, there is a clear advantage to our method in that we use over 200 times less training data.”

We greatly appreciate your effort to understand the paper. We have incorporated the suggested comments and believe it has significantly improved thanks to your feedback.

References

Lai, Junyu, et al. "Executing arithmetic: Fine-tuning large language models as Turing machines." arXiv preprint arXiv:2410.07896 (2024).

Reviewer_xHHFOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a framework for learning deterministic Turing-machine programs from input-output examples. The method uses a learned policy to guide the search over nondeterministic program traces, which are then converted into deterministic and verifiable programs. The authors evaluate their approach on algorithmic tasks including copy, reverse, binary addition, and multiplication, demonstrating improved search efficiency over a deterministic program-search baseline.

Critical strengths

The paper is well written and easy to follow. The proposed framework and its main components are clearly explained.

Critical weaknesses
  1. Unconvincing motivation and limited significance. The authors state that "The difficulty of verifying the correctness of such programs prompted us to investigate a different line of work." However, I am not convinced by this motivation. I do not see why the difficulty of verifying LLM reasoning justifies pursuing a relatively traditional and constrained Turing-machine program synthesis framework. In my view, improving the reasoning and verification capabilities of modern LLMs is a more promising and practically relevant direction. The paper does not provide a compelling argument for why this alternative line of work is useful or what important capabilities it offers beyond existing approaches.

  2. Insufficient comparison with modern methods. Given the motivation, I would expect comparisons with modern LLM-based coding agents or program synthesis methods on more challenging benchmarks. The current experiments mainly compare against a deterministic program-search baseline and older neural algorithm-learning approaches. A relevant benchmark is CodeARC [1], which evaluates LLM agents on inductive program synthesis. Without such comparisons, it is difficult to assess the significance of the proposed framework relative to existing capabilities.

[1] Wei, Anjiang, et al. "CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis." arXiv preprint arXiv:2503.23145 (2025).

Questions for authors

See weakness

3 comments

Thank you for the review. We are glad you found the paper easy to read and well explained. We respond to the weaknesses below.

Motivation and Significance. We agree that looking into reasoning in LLMs is a promising research direction, but it is also well served by many companies and research groups. We are pursuing a different direction that doesn’t require large amounts of data or large models. Each of our models is trained from scratch on very small data – there is no pretraining. If we restrict ourselves to only LLM-based research, we might never find technology that is different from what we already have.

In addition, our work is aimed at the discovery setting, without the strong supervision of what needs to be performed at every computational step. In this setting, we are aiming to achieve a type of generalization that is different from simply increasing the amount of pretraining data. While LLMs are powerful, we believe that it is worthwhile to explore other approaches that do not require such expensive amounts of data.

We agree that the original sentence you refer to from the abstract does not appropriately represent our motivation. We have rewritten it to: “The difficulty of verifying the correctness of such programs, along with large data requirements and inconsistent length generalization, prompted us to investigate a different line of work.” We view the discussion on the direction as a matter of research taste, and not a flaw of the paper. (Perhaps even as a strength!) Despite this, we kindly ask that the paper be viewed as a research contribution, and restate the key differences and contributions:

  • The synthesized programs are explicit and can be inspected or formally verified, unlike LLM reasoning traces.
  • A correct Turing-machine program generalizes to all input lengths, with no out-of-distribution failures.
  • Our method does not depend on pretraining data, so there are no contamination or memorization concerns.
  • The constrained setting allows precise claims about what is learnable and at what cost.

Comparison with Modern Methods. We thank the reviewer for the suggestion. We believe that within methods that make similar assumptions, we have adequately compared to the state of the art, namely Neural GPU (Kaiser et al., 2015).

CodeARC is a benchmark of general-purpose Python functions with an interactive query protocol specifically designed for LLM agents (Wei et al., 2025); whereas our framework builds Turing machine programs and cannot be meaningfully compared, given the large discrepancy in the amount of data used to train LLMs and our system. Prior work by Li et al. (2024, Section 6) suggests studying smaller, more efficient neural networks rather than LLMs. This is what we do. We believe that LLMs would solve all our problems quite easily, but that is beyond the point of our work. They require substantially more data, time, and compute to be trained. Our aim is not to outperform LLMs on these tasks but to study learning algorithms from examples alone, with verifiable outputs.

We would like to ask whether the concern is about our research taste and direction, or whether you have issues or questions about the method and study. We really appreciate the feedback and wonder whether we may be misunderstanding the issues raised.

References

Kaiser, Ł., & Sutskever, I. (2015). Neural GPUs learn algorithms. arXiv preprint arXiv:1511.08228.

Wei, Anjiang, et al. "CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis." arXiv preprint arXiv:2503.23145 (2025).

Li, W. D., & Ellis, K. (2024). Is programming by example solved by LLMs? Advances in Neural Information Processing Systems, 37, 44761-44790.

Thank you for the clarification. I agree that exploring alternative directions beyond LLMs is worthwhile. However, I think the paper would be more compelling if it demonstrated the value of this direction in a more practical or challenging setting, where existing LLM-based approaches face meaningful limitations. In particular, the choice of benchmarks should better highlight the unique advantages of the proposed approach, rather than focusing on tasks that LLMs can already solve easily. My concern is therefore about the practical significance and empirical motivation of the work. So I will maintain my score.

Thank you for taking the time to read our response and providing a follow-up. We respectfully disagree that focusing on LLM failure cases is methodologically helpful for discovering technology that is different from LLMs. As mentioned in our rebuttal, many researchers are already looking at those failure cases. That is why we are looking elsewhere, which includes problems that are challenging to solve in the small-data regime, even if LLMs can solve them.

Reviewer_HLtDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes learning programs for a designed Turing-like machine through execution-trace search. A learned policy chooses undefined transitions, while a shared table keeps decisions consistent across input-output examples. The system trains on selected traces and uses curricula and restarts to discover deterministic programs. Experiments cover string manipulation, addition, and multiplication, and the authors report Lean 4 correctness proofs for the discovered programs.

Critical strengths
  1. Returning explicit programs makes the results inspectable and allows formal verification beyond testing on longer inputs. The paper reports Lean 4 proofs and states the operand-length restriction for addition.

  2. The method discovers programs from small example pools. Copying succeeds in all ten seeds with lower mean discovery time than the baseline, advanced-machine addition succeeds in eight of ten seeds, and a multiplication program is found using 870 examples.

Critical weaknesses
  1. The comparison does not clearly establish that nondeterministic trace search is responsible for the improvement. The proposed method also introduces learned guidance, curricula, incremental table construction, and a different scoring objective. Although the baseline already uses execution feedback to modify visited table entries, it does not learn a policy.

  2. Reliable discovery remains difficult on multiplication: only one of ten seeds succeeds within 40 hours, and that run takes 129,240 seconds on the advanced machine. I appreciate that the authors report this limitation clearly. My concern is whether the method can find such programs consistently within a practical budget; the small number of distinct examples does not by itself answer this question.

Questions for authors
  1. Does the advantage persist under a common scoring objective? What happens when policy learning is disabled while keeping the proposed trace construction, curriculum, and restart rules?
  2. Can the authors provide solve-time curves for all ten seeds, separately for the base and advanced machines?
  3. Do the released executor and Lean specifications both use the undefined-transition halting rule described in Section 5.3? How is the addition length restriction handled at execution time, and which theorem declarations and commands reproduce the proof checks?
4 comments

We appreciate your time spent reviewing our work and providing constructive feedback.

W1. The comparison does not clearly establish that nondeterministic trace search is responsible for the improvement. Although the baseline already uses execution feedback to modify visited table entries, it does not learn a policy.

You are correct that our baseline comparison conflates two axes: deterministic search over programs vs. nondeterministic search over traces, and no learning vs. learning. To address this, we present an ablation showing the performance of our deterministic search baseline augmented with learning in the updated paper (Table 2), so we can better compare deterministic search to nondeterministic search.

We initialize the program tables based on the policy probabilities, which are trained across restarts, and then we run the same exhaustive beam search. This makes the learnt policy act as a deterministic program generator. The results show that this type of search performs better than the original beam search baseline, but not as well as our nondeterministic policy-based method.

These experiments provide evidence that while simply searching over deterministic programs using our original baseline is quite inefficient (cf. needle in a haystack); with learning we can greatly improve our performance. However, the results still show that our nondeterministic method can find solutions even more efficiently.

The proposed method also introduces learned guidance, curricula, incremental table construction, and a different scoring objective.

We additionally update the paper with ablations in Appendix I that show the impact of consistency arising from the incremental table construction (without the shared table representation, the policy does not solve any problems at all), and, in addition, we have updated the beam search baseline to be more in line with our method: it uses the same scoring function, the same curriculum, and the same verification pass before returning the final program. The difference in scoring functions was an oversight and led to an unfair comparison; thank you for bringing this to our attention. The baseline’s performance improves slightly, but the conclusions remain the same: our method performs better. Please let us know whether this addresses your concern.

W2. Reliable discovery remains difficult on multiplication: only one of ten seeds succeeds within 40 hours, and that run takes 129,240 seconds on the advanced machine. I appreciate that the authors report this limitation clearly. My concern is whether the method can find such programs consistently within a practical budget; the small number of distinct examples does not by itself answer this question.

Our result is significant. Learning addition and multiplication from scratch are challenging problems (Trask et al., 2019; Bai et al., 2025), and existing approaches require orders of magnitude more data (Kaiser et al., 2015). Despite the original Neural GPUs paper claiming that the learned models generalize, later work showed that they evaluated on randomly sampled inputs and don’t actually generalize – they fail on various edge cases (repeated digits, leading zeroes, etc., Price et al., 2016). We think that a single provably generalizable result is still much more consequential than many results that do not generalize.

Regarding computational efficiency, consider the following thought exercise. The different runs of our method can be seen as a single successful run with restarts, improving the perceived consistency. Our search is highly parallelizable, so it scales gracefully with the number of CPUs, allowing us to further reduce the wall-clock time to a potential solution. We acknowledge this limitation of our method, as solutions for challenging problems still require a significant amount of compute, and ask that you consider that it is still making a contribution toward more efficient discovery of algorithms.

We respond to your other questions in the next comment.

References

Trask, A., Hill, F., Reed, S. E., Rae, J., Dyer, C., & Blunsom, P. (2018). Neural arithmetic logic units. Advances in neural information processing systems, 31.

Bai, X., Pres, I., Deng, Y., Tan, C., Shieber, S., Viégas, F., Wattenberg, M., & Lee, A. (2025). Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls. arXiv preprint arXiv:2510.00184.

Price, E., Zaremba, W., & Sutskever, I. (2016). Extensions and limitations of the neural GPU. arXiv preprint arXiv:1611.00736.

Kaiser, Ł., & Sutskever, I. (2015). Neural GPUs learn algorithms. arXiv preprint arXiv:1511.08228.

Q1. Does the advantage persist under a common scoring objective?

We provide a set of ablations in response to W1, please see above. In summary, our method’s advantage does indeed persist under a common scoring objective.

What happens when policy learning is disabled while keeping the proposed trace construction, curriculum, and restart rules?

We include a no-learning ablation in Section 5.4 to address this: the ablation disables the training of the policy while keeping everything else the same. Without learning, we can solve no problems at all; there is no longer any gradient to guide the search through the large space of program traces.

Q2. Can the authors provide solve-time curves for all ten seeds, separately for the base and advanced machines?

This is a great idea, the solve curves are now in Appendix H of the revised version. The plots show the running best number of training problem instances solved within each rollout over time (out of 20). We use the running best because the plots become much too noisy if we show the exact number of solved tasks at every second. We also mark when each seed solves all of its training instances. For addition and multiplication, because we have a curriculum, we represent each level as 20 new instances stacked on top of previous levels. So, for example, solving 10 instances in level 2 of a curriculum would appear on the plot as solving 30 instances (20 from level 1, and 10 from level 2). A drop in the number of solved tasks indicates a demotion of the curriculum level. From these, we can see that seeds can complete throughout the entire duration of a run, both very close to the start and very close to the timeout, meaning longer timeouts may result in even more successes.

Q3. Do the released executor and Lean specifications both use the undefined-transition halting rule described in Section 5.3?

Yes, the Lean proofs rely on the undefined-transition halting rule, described in Section 5.3. The executor (assuming you mean the implementation of our method) does not rely on this rule – instead it halts when the verifier detects the output tape matches the ground truth output.

To further address the limitation of relying on the undefined-transition halting rule, we add results with learned halting (Appendix J) – in this case, the proofs no longer rely on the halting rule, and halting is covered by the program explicitly.

How is the addition length restriction handled at execution time?

The addition length restriction is not handled at execution time; it is assumed by our proof that operand a≠[]a \neq [] (hane in line 486 of the original addition.lean) and ∣a∣≤∣b∣|a| \leq |b| (hlen in line 486). The addition-length restriction was in place because our training and test data distribution did not cover certain input shapes, so at execution time there was no need for the program to handle such cases. We have worked to fix this restriction, and in the revised version of the paper, by ensuring a more diverse training distribution, we are able to generate programs that no longer have such a restriction; the results in Table 2 have been updated (with similar rates of success) along with an updated Lean proof of the program table in Appendix Table E.5 included in the supplementary material (addition_v2.lean).

Which theorem declarations and commands reproduce the proof checks?

To reproduce the proof checks, run the lean proofs with command lean, e.g., for addition, run lean addition_v2.lean. We have included these instructions in Appendix F. The key theorem in this file is add_correct.

We hope we have answered your questions and once again thank you for the feedback.

Thank you for adding the learned deterministic baseline, aligning the scoring and curriculum, and providing the additional ablations. These changes substantially improve the comparison. The explanation of the original executor's stopping rule, together with the reported learned-halting results and revised addition proof, also addresses important parts of my questions.

My remaining concern is reliable discovery within a practical total budget. Viewing the independent runs as restarts does not reduce the total computation, and parallelism reduces wall-clock time by using additional resources. I appreciate the value of discovering explicit, verifiable programs, but this reliability concern still affects my assessment. I currently remain at weak rejection.

Thank you for reading our response and recognizing that the paper has improved.

Regarding your remaining concern about the computational budget for discovering solutions, we believe that the compute requirements for solving these problems are reasonable. We do not use GPUs in our experiments; the whole pipeline runs on CPUs only and scales well with the number of CPUs. While it is difficult to compare with Neural GPUs because they do not report several details regarding computational cost, such as the number of training steps, they clearly state that they ran the system several times and that only a few runs were successful. What we know is that, in some cases, we use 200x less data than they did. At least on the data-usage axis, we can reliably say that we have substantially improved over previous work.

Regarding absolute running time, we acknowledge that reducing it can definitely be valuable. However, we would like to provide some context on why our current budget could still be considered reasonable. We are fine with a system running for days, or even months, if the goal is to discover algorithms (our experiments run for up to two days). In that case, we don't see running time as a significant problem because it has an amortized cost. That is, once an algorithm is discovered, it can be used to solve a very large number of problems. As the number of problems it solves grows, the cost of finding the algorithm goes to zero. In practical terms, we are fine waiting a long time if the outcome is an algorithm we can reuse over and over again.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Changes

We thank all the reviewers for their constructive feedback. We are happy to see that they find the paper well-written and the method strong. We have included several updates in the revised paper that we have uploaded to OpenReview (marked in blue text) and would like to provide a short summary:

  • We revise several claims that xHHF and mcym brought to our attention regarding the motivation and comparison against prior work.
  • Following the feedback from HLtD and mcym, we update our baseline to be more in line with our method by using the same scoring function, curricula and verification pass and also include a modified version of our baseline that makes use of a learned policy to provide a fair comparison of nondeterministic and deterministic search.
  • We include ablations to demonstrate the importance of different components of our method, as suggested by mcym.
  • We provide solve curve plots for our method as recommended by HLtD, showing the running best number of problem instances solved within a rollout over time.
  • Inspired by HLtD’s questions about the Lean proofs, we rerun our addition experiments with an updated training data distribution such that the discovered programs can be proven correct for any input a+ba+b (previously required ∣a∣≤∣b∣|a| \leq |b|), and also add experiments with learned halting, removing the need for a verifier at test time.

We provide detailed responses to each reviewer below. We thank the reviewers for their valuable reviews, we truly feel that the paper has improved greatly because of their feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.