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

Marco Dos Santos, Vivek Veeriah, Alex Havrilla, Andrew Bolt, Goran Zuzic, Satinder Singh, Tom Zahavy

A Gemini agent pipeline discovered and formally proved closed systems of Collatz-like acceleration rules for eleven specified six-state, two-symbol Turing machines. Each system summarizes exact execution from its fixed blank-tape starting configuration; the machines’ eventual halting behavior remains unresolved.

Sources for this record

What was already known

The authors distinguish eleven new machine analyses from fifteen rediscoveries of community-known acceleration patterns. The result concerns exact transition descriptions, not a value of BB(6) or a solution of the halting problem.

AI involvement AI-autonomous

Gemini 3.1 Pro agents generated patterns, conjectured transition rules, refined and proved them in Lean within a human-built pipeline. The authors report manual validation of final machine, starting-configuration and closure statements, after the autonomous discovery.

Importance Notable

Adds exact mathematical descriptions of previously unanalyzed Busy Beaver holdouts.

Limitations

The paper’s Cryptid classification is provisional and awaits community acceptance. New acceleration rules do not resolve whether these machines halt. Broader repository conjecture-checking machines and other rediscoveries are outside this contribution.

Technical verification Formal (Lean)

The authors report Lean verification against fixed machine definitions, fixed reachable starting configurations and closed rule systems. The pinned public library states standard-axiom kernel checking; this is source-reported, not a local rebuild. The exact check execution date is not supplied; the paper date is retained separately.

Formal checking

The authors report Lean verification against fixed machine definitions, fixed reachable starting configurations and closed rule systems. The pinned public library states standard-axiom kernel checking; this is source-reported, not a local rebuild.

Checker
Authors’ Lean 4 verification
Scope
Only the eleven new BB(6) acceleration systems in Appendix A: fixed machine/start definitions, proved transition rules and closure. No general halting or Busy Beaver value claim.
Basis
Reported by the linked checker
Evidence source

Checking a formal statement does not establish that it matches the original problem.

Human understanding Few

Few is the default when evidence for a higher level is insufficient. Manual validation of the final formal statements is documented, but a named human explanation of the central proof for each of the eleven new acceleration systems is not established. Few is the evidence default.

Correction and publication history

2026-10-19 · publication

Added this sourced contribution with its stated scope, AI attribution, checking evidence and research limits.

Read this published revision