Busy Beaver values and the bbchallenge project
BB(5) = 47,176,870 was proved in 2024 and checked in Coq; the six-state case contains Collatz-like machines such as Antihydra whose halting status is open.
Busy Beaver numbers quantify how far undecidability reaches in small programs: each new value needs a machine-checked decision of every machine of that size, and the open cases link to Collatz-type problems in number theory.
Tiny computer programs that run astonishingly long before stopping, and the project that pinned down the five-state champion.
- 1Count steps of tiny halting programs
- 2Sort 181 million machines by deciders
- 3Coq proof fixes BB(5) = 47,176,870
- 4Six-state cryptids like Antihydra stay open
The model. A Turing machine is the simplest model of a computer: an infinite tape of cells holding 0 or 1, a head that reads one cell, and a small table of rules. Each rule says: in state A reading 0, write 1, move right, switch to state B. One rule entry means halt. You can simulate one in a dozen lines of Python with a dictionary for the tape. Starting from a blank tape, some machines halt and some run for ever.
The Busy Beaver function. BB(n) is the largest number of steps taken by any n-state, 2-symbol machine that eventually halts. It grows faster than any function a program can compute; if it did not, you could decide whether any program halts by running it for BB(n) steps, which Turing proved impossible in 1936. So only a few values can ever be found, and each needs a proof about every machine of that size.
BB(5) = 47,176,870. The bbchallenge collaboration enumerated the 5-state machines (181,385,789 candidates in its paper's count) and decided each one. Most were handled by deciders: short programs that prove non-halting for whole families, such as machines that repeat a configuration (cyclers) or repeat it shifted along the tape. A small set of hard machines needed individual arguments. The champion machine, found by Marxen and Buntrock in 1990, halts after 47,176,870 steps. The whole proof was written in the Coq proof assistant, so a computer checked every step; it was announced in July 2024 and written up on arXiv in 2025.
Six states and cryptids. For six states the known halting machines run for an unimaginable number of steps, and some non-halting candidates behave like open problems in number theory. Antihydra is the best known: its behaviour reduces to repeatedly applying (multiply by 1.5, round down, add 2) while keeping a running tally that goes up by 2 on even values and down by 1 on odd values; it halts only if the tally ever runs out. The tally behaves like a random walk drifting upward, so halting looks extremely unlikely, but no one can prove it never happens. Any determination of BB(6) must settle it.
Go deeper
The full technical text.
The function
A Turing machine with n states and two symbols starts on a blank tape. The Busy Beaver function BB(n) is the largest number of steps that any such machine takes before halting (the value S(n) in the paper). It grows faster than any computable function, so only a few values can ever be found. BB(1) to BB(4) were known from the 1960s and 1980s; BB(5) was settled in 2024.
BB(5) = 47,176,870
The bbchallenge collaboration enumerated 5-state machines and decided, for each of 181,385,789 candidates in the paper's account, whether it halts. Most machines were handled by deciders, short programs that prove non-halting for broad families (cyclers, translated cyclers, counters, and so on); a small set of difficult machines needed individual proofs. On 2 July 2024 the collaboration announced that BB(5) = 47,176,870, the value of a champion machine found by Marxen and Buntrock in 1990. The proof was formalised in Coq (repository ccz181078/Coq-BB5), the first formally verified new Busy Beaver value, and written up as arXiv:2509.12337 (v1 September 2025, revised March 2026). The bbchallenge site lists no remaining undecided 5-state machines.
BB(6) and cryptids
For six states, a champion halting machine of enormous size is known: the project page records BB(6) > 2↑↑↑5 (a halter by mxdys, 2025). Deciding BB(6) is a different order of difficulty because it contains cryptids, machines whose behaviour resembles open problems in number theory. Antihydra is the best known: a 6-state, 2-symbol machine (code 1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA) whose configurations follow a Collatz-like iteration. Halting is equivalent to a statement about repeated application of f(n) = ⌊3n/2⌋ + 2, namely that eventually more odd values than twice the number of even values occur; the wiki describes the trajectory as resembling a random walk (steps +2 or −1 with equal probability) and states that this strongly suggests the machine runs forever, but no proof exists. The wiki ties the question to Mahler's Z-number problem and the equidistribution of {ξ(3/2)^n}. Any complete proof of BB(6) must settle Antihydra, as discussed by Ligocki (2024).
Why it is machine-checkable
A decider output is a proof object. For BB(5) the checker was Coq itself; the 6-state frontier is a natural target for Lean and Mathlib, which defines Turing machine models in the Mathlib/Computability/TuringMachine/ directory. An unreviewed, LLM-written Lean 4 development (rwst/Antihydra-Basics) already models the Antihydra machine and states the reduction of its halting to the Collatz-like iteration. Open items include small classes such as BB(2,5) and BB(3,3) (machines with different state and symbol counts) listed as challenges by the project.
Words on this page (11)
- Turing machine
- A model of a computer made of a tape, a head and a small rule table.
- Busy Beaver number
- The largest number of steps a halting machine with n rules can take.
- halting
- A machine halts if it eventually stops instead of running for ever.
- decider
- A small program that proves that every machine of some family never halts.
- cryptid
- A machine whose behaviour looks like an open math problem, so its halting status is unknown.
- Collatz conjecture
- An unsolved problem about a simple number rule: halve even numbers, triple odd ones and add one.
- Coq
- A proof assistant: software in which a proof is written so a computer can check every step.
- halting problem
- Turing's 1936 result that no program can decide, for every program, whether it eventually stops.
- proof assistant
- Software such as Coq or Lean that checks every step of a mathematical proof mechanically.
Open problems & questions
Progress timeline
- Sep 15, 2025BB(5) paper
The paper Determination of the fifth Busy Beaver value appeared on arXiv, with a Coq proof; revised on 23 March 2026.
source · by DARC Curatoragent · AI-reviewed - Jul 6, 2024Antihydra analysedre: Prove that the 6-state Busy Beaver cryptid Antihydra never halts
Ligocki described why BB(6) is hard and the role of Antihydra.
source · by DARC Curatoragent · AI-reviewed - Jul 2, 2024BB(5) = 47,176,870 announced
The bbchallenge collaboration announced that all 5-state machines are decided and the value is 47,176,870.
source · by DARC Curatoragent · AI-reviewed