# Busy beaver
The busy beaver function, introduced by [Tibor Radó](https://www.edgepedia.org/tibor-rado) in 1962, maps the number of states *n* of a [Turing machine](https://www.edgepedia.org/turing-machine) to the maximum number of steps, or alternatively the maximum number of 1s written on the tape, that any *n*-state, two-symbol machine can achieve from a blank tape before halting.[1](https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x) • [2](https://mathworld.wolfram.com/BusyBeaver.html) It is a concrete example of a well-defined function that no algorithm can compute, and it grows faster than any computable function.[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/)
| Key fact | Detail |
|---|---|
| Origin | Defined by Tibor Radó, "On Non-Computable Functions," Bell System Technical Journal 41: 877–884, May 1962[1](https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x) |
| Two functions | Σ(n), the maximum number of 1s left on the tape (Rado's sigma function), and S(n), the maximum number of steps before halting[2](https://mathworld.wolfram.com/BusyBeaver.html) |
| Known values of S(n) | 1, 6, 21, 107 for n = 1, 2, 3, 4; S(5) = 47,176,870 proved in 2024[2](https://mathworld.wolfram.com/BusyBeaver.html) • [4](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237) |
| Known values of Σ(n) | 1, 4, 6, 13 for n = 1, 2, 3, 4; Σ(5) = 4,098 proved in 2025[2](https://mathworld.wolfram.com/BusyBeaver.html) • [5](https://arxiv.org/abs/2509.12337) |
| Growth | Exceeds every computable function eventually; S(6) > 2↑↑↑5 in Knuth up-arrow notation[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/) • [2](https://mathworld.wolfram.com/BusyBeaver.html) |
| Logical strength | A 748-state machine (later improved to 745) halts if and only if Zermelo–Fraenkel set theory is inconsistent, so BB(748) cannot be proved in ZFC[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/) |
## Definition
Radó considered Turing machines over the alphabet {0, 1} with a two-way infinite tape, states labeled 1 through n, and starting in state 1 on an all-zero tape.[6](https://www.cs.umd.edu/~gasarch/open/busybeaver.pdf) The game is to run all n-state two-symbol machines, keep only those that eventually halt, and award the title to the halting machine that leaves the most 1s on its tape; that maximum is Σ(n). Radó also introduced S(n), the maximum number of steps made by a halting n-state machine from the all-zero tape.[5](https://arxiv.org/abs/2509.12337) Some authors use "busy beaver" for the winning machine itself and reserve the function names for the maxima; the notation BB(n) has historically meant Σ at some times and S at others.[5](https://arxiv.org/abs/2509.12337)
The two functions differ because the machine that runs longest need not be the one that writes the most 1s. For n = 5 the step champion writes 4,098 ones in 47,176,870 steps.[5](https://arxiv.org/abs/2509.12337)
## Why the function is uncomputable
Radó proved the function uncomputable by a maximization argument rather than diagonalization: the set of halting n-state machines is finite and non-empty, so it has a largest element, but no algorithm can produce that element for arbitrary n.[1](https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x) The connection to the halting problem is direct. If an algorithm computed the busy beaver function, then given any k-state machine M one could compute BB(k), run M for that many steps, and declare M a non-halter if it had not stopped by then; a machine that runs longer than every halting k-state machine never halts.[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/) • [7](https://content.wolfram.com/sites/13/2018/02/25-4-4.pdf)
The same argument bounds what mathematics can prove. Any function written down as a computer program is eventually exceeded by the busy beaver function, and knowing a sufficiently large busy beaver value would settle the halting status of every machine of that size or smaller.[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/)
## Known values and the BB(5) proof
The first values of Σ(n) are 1, 4, 6, 13, and the first values of S(n) are 1, 6, 21, 107.[2](https://mathworld.wolfram.com/BusyBeaver.html) The three-state case was settled by Lin and Radó in 1965, and the four-state case by Allen Brady in 1983.[2](https://mathworld.wolfram.com/BusyBeaver.html) In 1989, Heiner Marxen and Jürgen Buntrock found a five-state machine that runs 47,176,870 steps and writes 4,098 ones, but whether any five-state machine could beat it remained open for decades.[5](https://arxiv.org/abs/2509.12337) In 2020, [Scott Aaronson](https://www.edgepedia.org/scott-aaronson), a theoretical computer scientist at the [University of Texas at Austin](https://www.edgepedia.org/university-of-texas-at-austin), conjectured in his survey "The Busy Beaver Frontier" that the Marxen–Buntrock machine was the true winner.[5](https://arxiv.org/abs/2509.12337) • [8](https://www.quantamagazine.org/how-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210/)
**The 2024 proof.** On July 2, 2024, the Busy Beaver Challenge (bbchallenge), a collaborative online project launched in 2022 and coordinated by Tristan Stérin, announced a proof that S(5) = 47,176,870.[4](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237) • [9](https://www.lemonde.fr/sciences/article/2024/07/17/mathematiques-le-defi-du-castor-affaire-resolu_6251337_1650684.html) Contributor mxdys wrote the proof in the Coq proof assistant, building on work by more than ten other contributors; independent Coq experts reviewed the theorem statement, and the proof compiles in roughly 10 hours on a standard laptop.[4](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237) The proof enumerates 181,385,789 five-state machines (reduced from the full space by symmetries) and runs custom programs called deciders, each specialized in recognizing a particular kind of non-halting behavior.[4](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237) • [5](https://arxiv.org/abs/2509.12337) The accompanying paper, released on arXiv in September 2025, also proves Σ(5) = 4,098 and S(2,4) = 3,932,964 for two-state, four-symbol machines, and notes that this was the first determination of a new busy beaver value in over 40 years and the first ever formally verified.[5](https://arxiv.org/abs/2509.12337)
## Beyond five states
The values explode immediately after n = 5. In May 2022, Pavel Kropitz constructed a six-state, two-symbol machine that runs for more than 10↑↑15 steps (a tower of fifteen 10s) before halting, and the proven lower bound on S(6) stands above 2↑↑↑5.[2](https://mathworld.wolfram.com/BusyBeaver.html) • [5](https://arxiv.org/abs/2509.12337) Deciding the remaining six-state machines, nicknamed "cryptids" by the bbchallenge community, would require settling questions as hard as open mathematical conjectures such as Collatz.[9](https://www.lemonde.fr/sciences/article/2024/07/17/mathematiques-le-defi-du-castor-affaire-resolu_6251337_1650684.html)
The function also measures the reach of formal axioms. [Yuri Matiyasevich](https://www.edgepedia.org/yuri-matiyasevich), Stefan O'Rear, and collaborators of Scott Aaronson constructed a 748-state machine, later improved to 745 states, that halts if and only if [Zermelo–Fraenkel set theory](https://www.edgepedia.org/zermelo-fraenkel-set-theory) is inconsistent; assuming ZFC is consistent, ZFC cannot prove that this machine runs forever, so the value of BB(748) is independent of ZFC.[3](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/) • [10](https://arxiv.org/abs/1605.04343) A related result shows that BB(15) is, to date, the smallest busy beaver value tied to a natural open problem in mathematics.[11](https://arxiv.org/abs/2107.12475) Aaronson's survey poses further open questions, including whether BB(20) is independent of set theory and whether it is decidable, given n, whether BB(n) is even or odd.[6](https://www.cs.umd.edu/~gasarch/open/busybeaver.pdf)
## Studying the monsters
Because champion machines run for astronomically many steps, ordinary simulation is useless for verifying them. James Harland of RMIT University introduced the "observant otter" heuristic, which analyzes a machine's execution trace for repeated patterns and uses them to certify termination after an extremely large number of steps; empirical results show the heuristic is effective for all known "monster" machines.[12](https://www.sciencedirect.com/science/article/pii/S0304397516303504) The bbchallenge deciders follow the same general strategy of recognizing structured non-halting behavior, classifying machines into families such as counters, fractals, helices, and bells.[5](https://arxiv.org/abs/2509.12337)
## References
1. [T. Rado (1962). On Non-Computable Functions. Bell System Technical Journal 41: 877–884.](https://onlinelibrary.wiley.com/doi/abs/10.1002/j.1538-7305.1962.tb00480.x)
2. [Busy Beaver, Wolfram MathWorld](https://mathworld.wolfram.com/BusyBeaver.html)
3. [The Busy Beaver and What Cannot Be Computed, Proof & Machine](https://proofandmachine.github.io/articles/the-busy-beaver-and-what-cannot-be-computed/)
4. [[July 2nd 2024] We have proved "BB(5) = 47,176,870", The Busy Beaver Challenge](https://discuss.bbchallenge.org/t/july-2nd-2024-we-have-proved-bb-5-47-176-870/237)
5. [Determination of the fifth Busy Beaver value, arXiv:2509.12337](https://arxiv.org/abs/2509.12337)
6. [Scott Aaronson (2020). The Busy Beaver Frontier, ACM SIGACT News](https://www.cs.umd.edu/~gasarch/open/busybeaver.pdf)
7. [A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory, Wolfram](https://content.wolfram.com/sites/13/2018/02/25-4-4.pdf)
8. [How the Slowest Computer Programs Illuminate Math's Fundamental Limits, Quanta Magazine](https://www.quantamagazine.org/how-the-slowest-computer-programs-illuminate-maths-fundamental-limits-20201210/)
9. [Mathématiques : le défi du castor affairé résolu, Le Monde](https://www.lemonde.fr/sciences/article/2024/07/17/mathematiques-le-defi-du-castor-affaire-resolu_6251337_1650684.html)
10. [A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory, arXiv:1605.04343](https://arxiv.org/abs/1605.04343)
11. [Hardness of busy beaver value BB(15), arXiv:2107.12475](https://arxiv.org/abs/2107.12475)
12. [James Harland (2016). Busy beaver machines and the observant otter heuristic, Theoretical Computer Science 646: 61–85](https://www.sciencedirect.com/science/article/pii/S0304397516303504)
---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Computability theory › Undecidability and halting results*
*Initially written Sep 17, 2026 · Reviewed: Sep 19, 2026; Sep 30, 2026; Oct 15, 2026 · Edited: Sep 19, 2026; Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*
*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*
License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license