Exact acceleration rules for six-state Busy Beaver candidate machines

For a specified six-state, two-symbol Turing machine started on a blank tape, can exact runs be summarized by a closed system of Collatz-like acceleration rules?

Why it matters and what counts as progress

Why it matters: Acceleration rules replace enormous step-by-step traces by mathematical descriptions of Busy Beaver candidate behavior.

What counts as progress: New exact rules with proofs matching the machine’s transitions and starting configuration; such rules alone do not determine eventual halting or the value of BB(6).

How the problem developed

1962 · Problem formulation [1]
Tibor Rado Introduced the Busy Beaver functions, whose growth is tied to the behavior of finite-state Turing machines.
15 Oct 2026 · Formal proof [2]
Google DeepMind Gemini-based agent pipeline Reported discovery and formal verification of closed acceleration rules for eleven specified six-state, two-symbol machines. The machines’ eventual halting behavior remains unresolved.

AI contribution

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.

AI involvementAI-autonomous

ImportanceNotable

Technical verificationFormal (Lean)

Human understandingFew