acceptodds
Under review as a conference paper at ICLR 2027

At the Limits of Computability: Steps Towards Autonomous AI Discovery on the Busy Beaver Frontier

Abstract

Recent breakthroughs in AI for mathematics—ranging from Olympiad medal performances to resolving long-standing open conjectures—have rapidly expanded what automated systems can achieve. Yet, because these benchmarks primarily target fixed, human-formulated problems, they raise a provocative question: could AI systems eventually exhaust the supply of known mathematical questions? To push beyond static challenges, we explore the Busy Beaver (BB) domain, an uncomputable frontier that is fundamentally open-ended. Because no general algorithm can compute the sequence of Busy Beaver numbers for all 𝑛, making advances on this uncomputable frontier likely demands the invention of entirely new mathematical techniques. In this paper, we introduce a novel, Gemini-based agentic pipeline designed to automatically find accelerations of Turing machines: a common technique used when classifying machine halting behavior. Our system integrates pattern recognition, automated conjecturing, informal mathematical reasoning, and formal theorem proving in Lean. With this framework, our system autonomously discovered and formally verified novel Collatz-like accelerations for five machines. Subject to community acceptance, we provisionally classify these machines as Cryptids, namely machines whose blank-tape executions admit exact, compact mathematical descriptions but whose halting behavior remains unresolved. These results advance the analysis of BB(6) holdouts on the Busy Beaver frontier and demonstrate the potential of autonomous AI systems for open-ended mathematical discovery in fundamental computer science.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Busy Beaver, Turing Machine, Conjecturing, Collatz, Math, Language Models, Lean, Formal Proving

Reviews

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

This paper works on auto research workflow with LLMs, especially Gemini 3.1 pro. They focus on the Busy Beaver number problem, which asks about how much steps can a terminating program of a fixed size run. Their agentic workflow combines both informal and formal methods, and established several concrete theoretical results on this problem.

Critical strengths
  • The major results in this paper is very sound as theoretical verifiable discoveries with formal verification. These are concrete contributions in the domain of fundamental computer science.
  • The main workflow adopted in the paper appears to be fairly simple, which gives it good scalability and broad potential for practical applications.
Critical weaknesses
  • This paper is not very informative for researchers in the AI community. These results demonstrate the improved capabilities of language models, but they offer limited guidance for future research on AI4Math and autonomous AI discovery. Overall, the paper does not provide sufficiently many new insights for researchers in the AI community.
  • The significance of the discoveries in this work appears to be overstated in some places (Line 086 - Line 089 in Page 2). Although further declared in conclusions, we still prefer more grounded and pragmatic presentation.
Questions for authors
  • What do you think researchers working on AI4Math can learn from this work that could meaningfully inform or benefit their future research?
1 comment

Thank you for your thoughtful review! We are glad you found the workflow simple and scalable. We have updated the manuscript accordingly, with all revisions marked in blue, and would sincerely appreciate it if you would consider updating your review in light of our responses below.

Q1 / W1. What can AI4Math researchers learn from this work?

We added three general takeaways, backed by new stage-wise ablations and a coding-agent baseline (new Sections 4.4 and 4.5, Tables 3 and 4, Appendix D), now also stated in the Abstract, Introduction, and Conclusion.

Out of the 21 Cryptids already found by the community, we evaluate on the 20 Cryptids whose pattern is captured by the pattern detection stage (at most 17 can be retrieved, as 3 have a growing number of symbol blocks rather than a fixed number of exponents), checking each conjectured Python rule against our C++ simulator across all initial-simulation transitions, a 200,000-step forward orbit, and up to 500 boundary and modular perturbations of the block exponents (Table 3):

MethodNumber of Cryptids Retrieved
Initial simulation only (pass@2)0
Initial simulation only (pass@16)2
Coding agent (pass@1)9
Coding agent (pass@2)11
Our pipeline (pass@2, N=5)17
  1. Employing an LLM agent to autonomously test conjectures on edge cases. Conjecturing from the initial 5M-step simulation alone matches 100% of observed transitions on 17 machines at pass@16, yet misses halting, boundary cases, or system closure on most of them, retrieving only 2 Cryptids (0 at pass@2). Increasing the number of interactive refinement turns N (up to 400 synthetic configurations per turn; Table 4, Appendix D; N=0 queries the simulator once before conjecturing) steadily lifts pass@2 retrieval to all 17 retrievable Cryptids:
Refinement turns N012345
Cryptids retrieved51014151517

Accuracy on observed data is a poor signal of correctness; conjectures must be tested where data is missing.

  1. Filtering candidates via informal proving before formal verification. Across 14 BB(6) candidates, running our generator-evaluator loop (M=4) on 214 conjectures that passed 100% empirical accuracy and 100,000-step orbit closure rejects 185 conjectures (86.4%) and retains 29 across 6 machines (a 7.4x reduction), all 6 of which (100%) succeed in Lean 4. Since formal verification takes up to 72 hours per run, this lightweight informal critique stage saves substantial compute.

  2. Structuring discovery into dedicated stages. Compared against a Gemini 3.1 Pro coding agent given the machine, detected pattern, initial transitions, and a Python REPL with our C++ simulator and all our compression tools at the same 1.70M-token budget (pass@2), our pipeline retrieves 17 vs. 11 Cryptids (Table 3). Inspecting failed coding-agent runs shows that it stops early on recursive rules (4 machines) and runs out of context budget on systems with four or more coupled counters (2 machines; Appendix D). Giving a model tools is not enough without structuring how it tests and refines hypotheses.

Transfer beyond Turing machines (new Appendix D.4, Tables 5-6). To evaluate generality, we also show that these takeaways transfer to a benchmark of 18 multi-variable integer recurrences (recovering loop-free O(1) closed forms from 24-30 restricted inputs by actively probing unseen boundaries, residues, and thresholds on a black-box evaluator): initial-sample fits match 100% of initial points on all 18 at pass@16 yet recover 0/18 globally, whereas interactive refinement recovers 17/18 (climbing from 7 at N=0 to 17 at N=5) vs. 13/18 for the REPL coding agent (with 36% fewer tokens), proving 6 in Lean 4.

W2. Overstated significance (Lines 086-089).

We removed the sentence on Lines 086-089 (Section 1, third paragraph) noting that major conjectures (Fermat's Last Theorem, the Riemann hypothesis, Goldbach's conjecture, ZF consistency) can be encoded as the non-halting of specific Turing machines. We also replaced the claim that our approach applies to any Turing-complete language (Section 1, sixth paragraph) with an explicit distinction between our Turing-machine-specific tape compression and our domain-general discovery stages (code-based rule synthesis, interactive edge-case testing, informal proof filtering, and Lean 4 formalization), and replaced the broad remarks in the Conclusion (Section 5) with a grounded summary of our verified BB(6) and BB(2,5) accelerations, concrete next steps (richer configuration representations, broader dynamical systems, and automated halting or non-halting proofs), and our three empirical takeaways.

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

The paper proposes a custom LLM-based pipeline for analyzing holdout Turing machines in the Busy Beaver framework, whose halting behavior remains unknown. The authors evaluate their approach on more than 1,000 holdouts from BB(6), identifying 51 promising candidates and successfully discovering and formally verifying Collatz-like dynamics for five previously unanalyzed machines.

Critical strengths

Potential Mathematical Contribution.

The authors identified more than 50 promising candidates for further mathematical analysis and discovered and formally verified previously unknown Collatz-like dynamics for five BB(6) holdout Turing machines. These results could be valuable to the Busy Beaver research community.

Potentially Interesting Testbed for AI-for-Mathematics Research.

The Busy Beaver domain provides a potentially interesting testbed for studying autonomous mathematical discovery. Given the substantial effort required to resolve BB(5), it would be interesting to investigate what kinds of agentic workflows and multi-agent organizations could make meaningful progress toward resolving BB(6) or subsets of its remaining holdouts.

Critical weaknesses

Limited AI Novelty and Insufficient Justification of the Proposed Pipeline.

While the paper presents a potentially interesting mathematical contribution, its significance for the broader AI research community remains unclear. The paper provides limited insights into AI capabilities or autonomous mathematical discovery. The main AI-related contribution is the proposed agentic pipeline, which largely combines components already established in the literature, with limited methodological novelty.

Moreover, the paper does not provide sufficient empirical evidence to justify the design of this pipeline. Why are these particular components necessary? Would a general-purpose coding agent, given access to the same tools and tasked with discovering and verifying accelerations for the holdouts, achieve comparable results? Without ablations or comparisons against simpler agentic baselines, it is difficult to assess the value of the proposed approach or identify generalizable insights for the AI community.

Questions for authors

How would a general-purpose coding agent perform on the same holdouts if given the same tools (e.g., simulator and Lean environment) and computational budget, but without the proposed specialized pipeline? Could such an agent achieve comparable results in discovering and formally verifying accelerations?

1 comment

Thank you for your thoughtful review! We appreciate that you see value in our results for the Busy Beaver community and the Busy Beaver domain as an interesting testbed for AI-driven discovery. We have updated the manuscript accordingly, with all revisions marked in blue, and would sincerely appreciate it if you would consider updating your review in light of our responses below.

Q1. How would a general-purpose coding agent perform with the same tools and budget?

It retrieves 11 Cryptids, against 17 for our pipeline (Section 4.4, Table 3, Appendix D). Out of the 21 Cryptids already found by the community, we evaluate on the 20 Cryptids whose pattern is captured by the pattern detection stage (at most 17 can be retrieved in our representation, as 3 have configurations with a growing number of symbol blocks rather than a fixed number of exponents). Each conjectured Python rule is checked against our C++ simulator across all transitions observed during the initial simulation, a 200,000-step forward orbit, and up to 500 boundary and modular perturbations of the block exponents. Each Gemini 3.1 Pro coding-agent run receives the machine description, detected pattern, initial transitions, and a persistent Python REPL with direct access to our C++ simulator and all our compression tools (without community analyses or Lean proofs), capped at 40 REPL turns and 850k tokens per attempt to match our pipeline's 1.70M-token maximum budget at pass@2:

MethodNumber of Cryptids Retrieved
Initial simulation only (pass@2)0
Initial simulation only (pass@16)2
Coding agent (pass@1)9
Coding agent (pass@2)11
Our pipeline (pass@2, N=5)17

Tools make the coding agent a strong baseline, but it misses 6 retrievable Cryptids: inspecting failed runs shows that it stops early once its rule fits a few manual tests on recursive rules (4 machines), and runs out of context budget on systems with four or more coupled counters (2 machines; Appendix D).

W1. Why are the components necessary?

We added ablations measuring the impact of each stage (Section 4.4, Appendix D) and distilled general takeaways (new Section 4.5).

Pattern detection. On the 21 Cryptids already found by the community, varying the cutoff K in {1, 10, 50, 100} of top-ranked compressed patterns passed to the rest of our pipeline retrieves 5, 11, 16, and 17 Cryptids. At K=100, this stage captures the target pattern for 20 of the 21 Cryptids (only 1 ranks beyond K=100, at rank 299), showing that frequency ranking surfaces nearly all target patterns while searching beyond K=1 is essential.

Interactive refinement. As shown in Table 3 above, conjecturing from the initial 5M-step simulation alone retrieves 0 Cryptids at pass@2 and 2 at pass@16, even though the conjectured rules match 100% of observed transitions on 17 machines (failing on unseen halting and boundary cases). Increasing the number of interactive refinement turns N (up to 400 synthetic configurations per turn; Table 4, Appendix D) steadily lifts pass@2 retrieval to all 17 retrievable Cryptids:

Refinement turns N012345
Cryptids retrieved51014151517

Here N=0 queries the interactive simulator once before conjecturing without subsequent revision turns, already improving over using the initial simulation alone (0 at pass@2).

Informal proving. Across 14 BB(6) candidates, we ran our generator-evaluator loop (M=4) on 214 conjectures that passed 100% empirical accuracy and 100,000-step orbit closure, sending only accepted candidates to Lean 4. Informal proving rejects 185 conjectures (86.4%) and retains 29 across 6 machines (a 7.4x reduction), all 6 of which (100%) succeed in Lean 4. Since formal verification takes up to 72 hours per run, this stage saves substantial compute.

Together, these ablations and the coding-agent comparison support three general takeaways for AI-driven mathematical discovery (new Section 4.5), now also stated in the Abstract, Introduction, and Conclusion: employing an LLM agent to autonomously test conjectures on edge cases, filtering candidates via informal proving before formal verification, and structuring discovery into dedicated stages. We further show that these takeaways transfer beyond Turing machines on a controlled benchmark of 18 multi-variable recurrences (synthesizing loop-free O(1) closed forms from 24-30 restricted evaluations by actively probing unseen boundaries, residues, and thresholds on a black-box evaluator), where our pipeline recovers 17/18 exact closed forms vs. 13/18 for the coding agent and 0/18 from initial data alone, proving 6 in Lean 4 (new Appendix D.4, Tables 5-6).

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

The paper proposes an agentic pipeline for discovering and formally verifying arithmetic accelerations of Busy Beaver machines. The pipeline combines pattern detection, LLM-based conjecturing, informal reasoning, and formal theorem proving in Lean. The authors report five new Collatz-like accelerations for BB(6) machines, along with four additional results for previously analyzed machines but these Collatz-like accelerations do not resolve the halting status of the machines.

Critical strengths
  1. The paper discovers and formally verifies new arithmetic rules for five BB(6) machines, which may be a useful intermediate result for the Busy Beaver problem.
Critical weaknesses
  1. I think the paper focuses too much on the BB machines themselves. The more interesting part for an ML conference is the discovery workflow, but the paper gives much more attention to the arithmetic results. While these may be useful intermediate results, I find their significance for an ML conference somewhat limited on their own.
  2. The proposed workflow is not studied enough. It's unclear why some of the components are needed or how much they actually contribute. The lack of baselines and ablations makes it difficult to judge the value of the proposed workflow.
  3. The workflow also seems very specific to BB machines. I'm not convinced by the claims about more general autonomous mathematical discovery.
  4. The writing is quite poor in my opinion. There is too much jargon, and many parts feel unnecessarily complicated. The use of direct hyperlinks in place of citations in some places is also strange for an academic paper.
Questions for authors

None

1 comment

Thank you for your thoughtful review. We are glad you found that our five new, formally verified BB(6) results may be a useful step for the Busy Beaver problem. We have updated the manuscript accordingly, with all revisions marked in blue, and would sincerely appreciate it if you would consider updating your review in light of our responses below.

W1. Too much focus on the machines rather than the discovery workflow.

We gave more focus to the discovery workflow and its analysis, adding stage-wise evaluations (Section 4.4) and general takeaways (Section 4.5, and Abstract, Introduction, Conclusion), and moving the discovered-machines table to Section 4.3 (Table 2).

W2. Unclear contribution of each component; no baselines or ablations.

We added stage-wise ablations and a coding-agent baseline (Section 4.4, Table 3, Appendix D) with Gemini 3.1 Pro on the 21 Cryptids (Table 1), checking each Python rule in C++ on initial transitions, a 200k-step orbit, and 500 boundary/modular perturbations.

Pattern detection. Varying the top-K pattern cutoff passed to our pipeline (pass@2, N=5) on the 21 Cryptids yields:

Pattern cutoff K11050100
Cryptids retrieved (of 21)5111617

At K=100, it captures the target pattern for 20/21 Cryptids (only 1 ranks at 299), lifting retrieval from 5 (K=1) to 17.

Interactive refinement and coding agent (Tables 3-4). On the 20 captured Cryptids (at most 17 retrievable, as 3 have growing block counts), we compare the 5M-step simulation alone, interactive refinement (up to 400 synthetic configs/turn), and a Gemini 3.1 Pro coding agent given the machine, pattern, initial transitions, and a Python REPL with our C++ simulator and compression tools (40 turns, 850k tokens/attempt, matching our 1.70M-token pass@2 budget):

MethodCryptids Retrieved
Initial simulation only (pass@2 / pass@16)0 / 2
Coding agent (pass@1 / pass@2)9 / 11
Our pipeline (pass@2, N=5)17

Initial-simulation rules fit 100% of observed data on 17 machines at pass@16 yet retrieve 2 due to missed halting/boundary cases, while our pipeline retrieves all 17 (+6 over the coding agent at equal budget). Varying refinement turns N (Table 4; N=0 queries once before conjecturing) lifts pass@2:

Refinement turns N012345
Cryptids retrieved51014151517

Informal proving. On 214 conjectures across 14 BB(6) candidates passing 100% accuracy and 100k-step closure, our generator-evaluator loop (M=4) rejects 185 (86.4%) and keeps 29 across 6 machines (7.4x reduction), all 6 (100%) proven in Lean 4 (up to 72h/run; saving substantial compute).

W3. Generality of the discovery workflow beyond Busy Beaver machines.

While tape compression is tailored to Turing machines, the rest of the discovery architecture is domain-general (Section 1, Section 4.5). To test this without Turing machines or tape compression, we ran the same workflow on 18 multi-variable integer recurrences across five families (divide-and-conquer, nested thresholds, block-periodic sums, 2D reflections, counter borrows; Appendix D.4, Tables 5-6), recovering a loop-free O(1) closed form across 550 test inputs from 24-30 points.

Example. For a hidden nested recurrence f(n, b) (f(0,0)=15, else 2*g(n, 26+5b) + 4*(b%3) + b^2 with g(n,T)=n-4 if n>T else g(g(n+7,T),T)), the input is 30 pairs on {1..15}x{1,2} (f(1,1)=65, f(2,1)=61, ..., hiding (0,0), b%3=0, and n > 26+5b), and the expected output is an O(1) Python closed_form(n, b) returning 15 at (0,0), 2*(n-4)+4*(b%3)+b^2 for n > 26+5b, and 2*(25+5b-((26+5b-n)%3))+4*(b%3)+b^2 otherwise. In each interactive refinement turn, the LLM proposes up to 400 inputs probing unseen boundaries, residues, and high thresholds, queries the black-box evaluator, and revises its formula on mismatches before informal and Lean 4 proving:

MethodClosed Forms Retrieved (of 18)
Initial sample only (pass@2 / pass@16)0
Coding agent (pass@1 / pass@2)10 / 13
Our pipeline (pass@2, N=5)17

Initial-sample fits match 100% of initial points on all 18 at pass@16 yet recover 0 globally, while refinement climbs from 7 (N=0) to 17/18 (N=5; 7, 12, 15, 16, 17, 17 for N=0..5), beating the coding agent (13/18) with 36% fewer tokens (331k vs. 519k) and proving 6 in core Lean 4 within 10 turns.

W4. Domain-specific terminology, clarity, and citations.

We replaced all inline hyperlinks with formal citations and defined domain-specific terms at first use: deciders (Section 1), Collatz-like systems (Section 1), and standard TM notation (Section 2.1), moved Table 2 after them (Section 4.3), and streamlined Section 3.4.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal summary: ablations, coding-agent baseline, and cross-domain transfer

We thank all reviewers and Area Chairs for their thoughtful feedback and constructive discussion. Our paper introduces a four-stage Gemini-based pipeline (pattern detection, interactive conjecturing, informal proving, and Lean 4 formal verification) that autonomously discovers and formally verifies Collatz-like accelerations for five previously unanalyzed BB(6) holdouts and four further machines. The reviews primarily asked for stage-wise ablations, a comparison with a general-purpose coding agent at equal budget, clearer AI4Math takeaways, evidence of transfer beyond Busy Beaver machines, and improved clarity and grounding. Our new experiments quantify each stage's contribution, show that our pipeline outperforms a tool-equipped coding agent at equal budget, and confirm that the workflow and takeaways transfer to multi-variable recurrences. We summarize these findings below. All manuscript changes are marked in blue, and our individual responses give further details.

1. How does our pipeline compare with a coding agent and simpler baselines at equal budget?

On the 20 community Cryptids whose pattern is captured by pattern detection (at most 17 retrievable, as 3 have growing block counts), we compare conjecturing from the 5M-step simulation alone, a Gemini 3.1 Pro coding agent with a persistent Python REPL, our C++ simulator, and all compression tools (40 turns, 850k tokens/attempt), and our pipeline at the same 1.70M-token pass@2 budget (verifying every rule in C++ over initial transitions, a 200k-step orbit, and 500 boundary/modular perturbations):

MethodCryptids Retrieved (of 20; max 17)
Initial simulation only (pass@2)0
Initial simulation only (pass@16)2
Coding agent (pass@1)9
Coding agent (pass@2)11
Our pipeline (pass@2, N=5)17

Our pipeline retrieves all 17 retrievable Cryptids (+6 over the coding agent at equal budget). Failed coding-agent runs either stop early on recursive rules (4 machines) or exhaust the context budget on systems with 4+ coupled counters (2 machines). See Section 4.4 (Table 3) and Appendix D.3.

2. How much does each stage of the pipeline contribute?

  • Pattern detection. Across all 21 community Cryptids, passing the top-K frequency-ranked patterns (K = 1, 10, 50, 100) retrieves 5, 11, 16, and 17 Cryptids, with K=100 capturing 20/21 target patterns (1 ranks at 299).
  • Interactive refinement. Initial-simulation rules match 100% of observed data on 17 machines at pass@16 yet retrieve only 2 Cryptids (0 at pass@2) due to missed halting/boundary cases. Adding refinement turns N (up to 400 synthetic configs/turn; N=0 queries once before conjecturing) lifts pass@2 retrieval (Table 4, Appendix D.2):
Refinement turns N012345
Cryptids retrieved51014151517
  • Informal proving. On 214 conjectures across 14 BB(6) candidates passing 100% accuracy and 100k-step closure, our generator-evaluator loop (M=4) rejects 185 (86.4%) and retains 29 across 6 machines (7.4x reduction), all 6/6 (100%) proven in Lean 4 (saving substantial compute at up to 72h/run; Section 4.4).

3. Do the workflow and takeaways transfer beyond Busy Beaver machines?

To test generality without Turing machines or tape compression, we ran the same workflow on 18 multi-variable integer recurrences across five families (divide-and-conquer, nested thresholds, block-periodic sums, 2D reflections, counter borrows): from 24-30 restricted evaluations, each method must synthesize a loop-free O(1) closed form across 550 boundary, modular, and OOD inputs by actively probing unseen regimes:

MethodClosed Forms Retrieved (of 18)
Initial sample only (pass@16)0
Coding agent (pass@2)13
Our pipeline (pass@2, N=5)17

Initial-sample fits match 100% of observed points on all 18 at pass@16 yet recover 0 globally. Interactive refinement climbs from 7 (N=0) to 17/18 (N=5; 7, 12, 15, 16, 17, 17 for N=0..5), beating the coding agent (13/18) with 36% fewer tokens (331k vs. 519k), and proves 6 in core Lean 4 within 10 turns (Appendix D.4, Tables 5-6).

4. Takeaways and presentation improvements.

We distilled three general takeaways in new Section 4.5 (and Abstract, Introduction, Conclusion): (1) employing an LLM agent to autonomously test conjectures on edge cases, (2) filtering candidates via informal proving before formal verification, and (3) structuring discovery into dedicated stages. We also replaced inline hyperlinks with formal citations, defined domain terms at first use (deciders, Collatz-like systems, TM notation), moved Table 2 after definitions (Section 4.3), removed overstated remarks (Section 1, Section 5), and streamlined Section 3.4.

Thank you again for helping us improve the paper!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.