💻 computer science

Determination of the fifth Busy Beaver value

This paper presents the first formally verified determination of the fifth Busy Beaver value, $S(5) = 47,176,870$ , achieved through a massively collaborative online effort using the Coq proof assistant to analyze over 181 million Turing machines.

Original authors: The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev, Matthew L. House, Rachel Hunter, Iijil, Maja Kądziołka, Pavel Kropitz, Sha

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: The bbchallenge Collaboration, Justin Blanchard, Daniel Briggs, Konrad Deka, Nathan Fenner, Yannick Forster, Georgi Georgiev, Matthew L. House, Rachel Hunter, Iijil, Maja Kądziołka, Pavel Kropitz, Shawn Ligocki, mxdys, Mateusz Naściszewski, savask, Tristan Stérin, Chris Xu, Jason Yuen, Théo Zimmermann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are running a massive, chaotic race. The runners are tiny, simple robots called Turing Machines. They have a very limited brain (a few "states") and a long, infinite strip of paper (the "tape") that starts out completely blank.

The rules of the race are simple:

The robot reads a spot on the paper, writes a new symbol (0 or 1), moves left or right, and changes its internal mood (state).
If the robot runs into a spot where it doesn't know what to do, it stops (halts).
The goal? To see which robot can take the most steps before stopping.

This is the Busy Beaver Game. The question is: "What is the maximum number of steps a robot with n states can take before it stops?"

For a long time, mathematicians knew the answers for robots with 1, 2, 3, and 4 states. But for 5 states, the answer was a mystery. It was like trying to guess the winner of a race where the finish line is so far away that you can't even see it, and some runners might run forever without stopping.

The Big Breakthrough

This paper is the story of how a massive online team of volunteers, called The bbchallenge Collaboration, finally solved the mystery for the 5-state robots.

They proved that the winner takes exactly 47,176,870 steps.

But here's the twist: They didn't just guess or run a simulation. They used a super-strict digital lawyer called Coq (a proof assistant) to check every single step of their logic. It's like having a robot judge that reads the entire race manual, line by line, to ensure no mistakes were made. This is the first time a Busy Beaver number has been verified this way.

How Did They Do It? (The Analogy)

Imagine you have a library with 16 trillion books. Each book describes a different robot. You need to find the one that runs the longest.

The Problem: You can't read 16 trillion books. Some robots run for millions of years; others run forever.
The Solution (Tree Normal Form): The team realized that many robots are just "twins" of each other (they do the same thing, just with different names). They built a family tree to group these twins together. This shrank the library from 16 trillion books down to a manageable 181 million. Still a lot, but doable with computers.

Next, they built a filtering machine (a pipeline of "deciders"). Think of this as a series of security checkpoints:

The Loop Detector: "Hey, this robot is walking in circles! It will never stop. Disqualified." (This caught the vast majority of robots).
The Pattern Matcher: "This robot is writing a repeating pattern that will never end. Disqualified."
The Math Prover: "This robot is doing something complex, but we can prove mathematically it will never stop."

Most robots were caught by the first two checkpoints. But 13 stubborn robots (called Sporadic Machines) were tricky. They didn't loop, and they didn't follow simple patterns. They were like wild animals that had to be studied individually.

One of them, named "Skelet #17", was the "Final Boss." It was so complex that it took a dedicated paper just to explain how it works. It was the last one to be tamed.

The "Cryptids" (The Monsters in the Woods)

The paper also talks about Cryptids. In the world of Bigfoot and Loch Ness Monsters, these are creatures people think exist but can't prove.
In the Busy Beaver world, a Cryptid is a robot that we think runs forever, but we can't prove it yet.

The team found that for 6-state robots, there are many Cryptids.
One of them is linked to a famous unsolved math problem (the Collatz Conjecture). Proving whether this robot stops is as hard as solving that math problem.
The authors joke that the "smallest open problem in mathematics" might be hidden inside a 6-state robot.

Why Should You Care?

It's a Team Effort: This wasn't done by one genius in a lab coat. It was done by hundreds of people (students, engineers, hobbyists) chatting on Discord, sharing code, and helping each other. It's like a massive open-source software project, but for math.
It's a Test for AI: The authors are now using this proof to test Artificial Intelligence. Can an AI figure out the logic behind these robots? So far, AI is doing okay, but it's a tough challenge.
The Limits of Knowledge: This paper shows us the edge of what we can know. We can prove the answer for 5 states, but for 6 states, the problems get so hard that they might be impossible to solve with our current math rules.

The Bottom Line

The team successfully hunted down the champion of the 5-state Busy Beaver race. They proved it runs 47,176,870 steps and then stops. They did this by building a digital fortress of logic that no one can argue with.

It's a victory for human curiosity, collaboration, and the power of computers to help us understand the limits of the universe. And while they solved the 5-state mystery, they also found a whole new forest of "Cryptids" in the 6-state world, waiting for the next generation of explorers to solve them.

1. Problem Statement

The paper addresses the determination of the Busy Beaver function $S(n)$ , defined as the maximum number of steps a halting $n$ -state, 2-symbol Turing machine can execute starting from an all-zero tape.

Context: $S(n)$ is a non-computable function. Prior to this work, only $S(1)$ through $S(4)$ had been rigorously proven ( $S(4)=107$ ).
The Challenge: Determining $S(5)$ requires analyzing the halting behavior of a vast search space. While the winning machine (discovered in 1989) runs for 47,176,870 steps, the primary difficulty lies in proving that no other 5-state machine runs longer or halts later. This involves proving the non-halting status of millions of machines, some of which exhibit complex, chaotic behaviors that mimic hard mathematical conjectures (e.g., Goldbach's conjecture or the Riemann hypothesis).
Goal: To formally prove that $S(5) = 47,176,870$ and $S(2, 4) = 3,932,964$ (for 2-state, 4-symbol machines) using a machine-verified proof.

2. Methodology

The authors employed a massive collaborative effort combined with formal verification using the Coq proof assistant. The methodology consists of three main pillars:

A. Search Space Reduction: Tree Normal Form (TNF)

To make the problem computationally tractable, the authors utilized Tree Normal Form (TNF) enumeration.

Reduction: Instead of analyzing the syntactic total of $\approx 1.67 \times 10^{13}$ (16.7 trillion) possible 5-state machines, TNF reduces the search space to 181,385,789 unique machines.
Technique: TNF recursively builds machines by defining transitions only when necessary, pruning unreachable transitions and eliminating machines that are merely permutations of states or symbols.
Implementation: The entire TNF enumeration and traversal were implemented directly within Coq, a significant departure from previous methods that relied on external, unverified enumeration.

B. The Decider Pipeline

The core of the proof is a pipeline of algorithms ("deciders") that attempt to determine if a machine halts or loops. Since the halting problem is undecidable, these are partial deciders; if one fails, the machine is passed to the next.

Loops (Algorithm 1): Detects standard cycles (Cyclers) and spatially translated cycles (Translated Cyclers) by analyzing the history of state-symbol-head position tuples rather than full tape configurations. This solved 95.48% of non-halting machines.
n-gram Closed Position Set (NGramCPS): An abstraction of the "Closed Position Set" technique. It tracks local configurations (n-grams of tape symbols) to prove that a machine enters a closed set of states from which it cannot escape to a halting transition. This solved 99.89% of the remaining non-halting machines.
- Augmentation: The authors enhanced this with "Fixed-length history" and "Least Recent Usage (LRU)" history to handle machines with complex tape dependencies.
Repeated Word List (RepWL): Uses regular expressions to represent tape configurations. If a block of symbols repeats more than a threshold $T$ , it is treated as an infinite repetition. This handles machines with fractal-like or periodic tape growth.
Finite Automata Reduction (FAR) & Weighted FAR (WFAR):
- FAR: A co-CTL (co-Closed Tape Language) technique using Non-deterministic Finite Automata (NFA) to prove that the set of halting configurations is disjoint from the initial configuration.
- WFAR: An extension using Weighted Finite Automata to handle non-regular languages, allowing the proof of non-halting for machines with more complex invariants.
Sporadic Machines: For the 13 machines that resisted all automated deciders, the team constructed individual, hand-crafted Coq proofs of non-halting. These machines exhibit unique behaviors (e.g., Fibonacci counters, Gray code obfuscation, and massive pre-period loops).

C. Formal Verification (Coq-BB5)

The Proof: The entire process is encapsulated in Coq-BB5, a formal proof script.
Reflection: The proof uses "proof by reflection," where Coq runs the verified algorithms (TNF enumeration and deciders) and uses their outputs to construct the final theorem.
Trust: The only external axiom used is functional_extensionality_dep, which is standard and consistent. The proof compiles in ~45 minutes on 13 cores.

3. Key Contributions

First Formal Verification of a Busy Beaver Value: This is the first time a Busy Beaver value has been determined with a machine-checked proof, eliminating human error in the verification of millions of cases.
Massive Collaborative Research: The project utilized bbchallenge.org, a platform where hundreds of contributors (mostly non-academic) developed deciders, analyzed "holdouts," and shared code in various languages (C++, Python, Rust, Haskell, etc.).
Algorithmic Innovations:
- Development of Algorithm 1 for loop detection using transcript analysis.
- Refinement of NGramCPS with tape augmentations (LRU/Fixed history).
- Introduction of WFAR for handling irregular non-halting machines.
Direct Coq Enumeration: Successfully implementing and running the TNF enumeration of 181 million machines directly inside the Coq proof assistant, a feat previously thought too computationally intensive.

4. Results

The paper confirms the following values:

$S(5) = 47,176,870$ : Proven by showing that the 1989 champion machine halts at this step count and all other 181,385,788 machines either halt earlier or never halt.
$\Sigma(5) = 4,098$ : The maximum number of 1s on the tape for a 5-state halting machine.
$S(2, 4) = 3,932,964$ : The value for 2-state, 4-symbol machines.
$S(4) = 107$ : Re-verified with formal proofs, confirming previous results.

Data Output:
The authors extracted a list of all 181,385,789 enumerated 5-state machines, their halting status, and the specific decider that solved them. This dataset is publicly available and allows for the computation of any observable metric on 5-state machines.

Sporadic Machines:
The 13 "Sporadic Machines" (e.g., "Skelet #1", "Skelet #17") were the hardest to solve.

Skelet #1: A Translated Cycler with a pre-period of $\approx 5.41 \times 10^{51}$ steps.
Skelet #10: A Double Fibonacci Counter.
Skelet #17: A machine implementing a complex Gray code transformation on a list of integers.

5. Significance

Mathematical Frontier: The work establishes that the "smallest open problem" in mathematics (in the context of Busy Beaver) does not lie with 5-state machines but likely with 6-state machines (specifically "Cryptids" like Antihydra, which are linked to the Collatz conjecture and likely unprovable in standard ZF set theory).
Collaborative Science: It demonstrates the efficacy of "open-source" mathematics, where distributed, non-academic collaboration can solve problems that were previously stalled for decades.
AI Benchmark: The generated open problems (Cryptids) and the formal proofs serve as benchmarks for AI reasoning tools. Early tests show AI systems solving 58% of the first 100 lemmas of the $S(4)$ proof.
Formal Methods: It sets a new standard for the scale of formal verification in theoretical computer science, proving that massive computational searches can be fully integrated into a trusted logical framework.

In summary, the paper resolves a 40-year-old open problem in computability theory by combining algorithmic innovation, massive distributed computing, and rigorous formal verification, effectively closing the chapter on 5-state Busy Beavers.