Main Page

2026-04-13T15:32:40Z

Crimsonneuron: less->fewer

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalised to ''m''-symbol Turing machines:<ref>Radó, T. (1962), On Non-Computable Functions. Bell System Technical Journal, 41: 877-884. https://doi.org/10.1002/j.1538-7305.1962.tb00480.x</ref><ref>Brady, Allen H, and the Meaning of Life, 'The Busy Beaver Game and the Meaning of Life', in Rolf Herken (ed.), The Universal Turing Machine: A Half-Century Survey (Oxford, 1990; online edn, Oxford Academic, 31 Oct. 2023), https://doi.org/10.1093/oso/9780198537748.003.0009, accessed 8 June 2024.</ref>

{| class="wikitable"
|-
| BB(''n'', ''m'') = Maximum number of steps taken by a halting ''n''-state, ''m''-symbol Turing machine starting from a blank (all 0) tape
|}

The 2-symbol case BB(''n'', 2) is abbreviated as BB(''n''). The busy beaver function is not computable, but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
! !!2-state!!3-state !!4-state!!5-state!!6-state
!7-state
|-
! 2-symbol
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" | [[BB(6)]] ≥ <math>2 \uparrow \uparrow \uparrow 5</math>
| style="background: orange;" | [[BB(7)]] ≥ <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|-
! 3-symbol
| [[BB(2,3)]] = 38
| style="background: orange;" | [[BB(3,3)]] ≥ <math>10^{17}</math>
| style="background: #ffe4b2;" | [[BB(4,3)]] ≥ <math>10 \uparrow^{4} 4</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 4-symbol
| [[BB(2,4)]] = 3,932,964
| style="background: #ffe4b2;" | [[BB(3,4)]] ≥ <math>2 \uparrow^{15} 5</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 5-symbol
| style="background: orange;" | [[BB(2,5)]] ≥ <math>10\uparrow\uparrow 4</math>
| style="background: #ffe4b2;" | [[BB(3,5)]] ≥ <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|-
! 6-symbol
| style="background: #ffe4b2;" | [[BB(2,6)]] ≥ <math>10 \uparrow\uparrow\uparrow 3</math>
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
| style="background: #ffe4b2;" |
|}

In the above table, <span style="background: orange">cells are highlighted in orange</span> when there are known [[Cryptids]] (mathematically-hard machines) in that class, and <span style="background: #ffe4b2">cells are highlighted in light orange</span> when the existence of a Cryptid is given by using a known one with fewer states or symbols.

1-state domains and 1-symbol domains are omitted in the table as [[BB(1,m)]] = 1 and [[BB(n,1)]] = n.

== About bbchallenge ==
[[bbchallenge]] is a massively collaborative research project whose general goal is to obtain more knowledge on the [[Busy Beaver function]]. In practice, it mainly consists in collaboratively building [[Deciders]], programs that automatically prove that some Turing machines do not halt. Other efforts also include:

* Formalising results using theorem provers (such as [https://en.wikipedia.org/wiki/Rocq Rocq])
* Maintaining [[Holdouts lists]] for small busy beaver values
* [[Analysis Tools and Techniques|Proving]] the behavior of [[:Category:Individual Machines|Individual machines]]
* Finding [[Cryptids]] (mathematically-hard machines)
* Searching for new [[Champions]]
* Building [[Accelerated Simulator]]s to simulate halting machines faster
* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]

In June 2024, bbchallenge achieved a significant milestone by proving in [https://en.wikipedia.org/wiki/Rocq Rocq] (previously known as Coq) that the 5th busy beaver value, [[BB(5)]], is equal to the lower bound found in 1989: 47,176,870.<ref>H. Marxen and J. Buntrock. Attacking the Busy Beaver 5.
Bulletin of the EATCS, 40, pages 247-251, February 1990. https://turbotm.de/~heiner/BB/mabu90.html</ref>

== This Month in Beaver Research (TMBR) ==
[[:Category:This Month in Beaver Research|This Month in Beaver Research]] (TMBR, pronounced "timber") is a monthly summary of Busy Beaver research progress. Here are the three most recent released entries:

* [[TMBR: January 2026]]
* [[TMBR: December 2025]]
* [[TMBR: November 2025]]

[[TMBR: February 2026]], [[TMBR: March 2026]] and [[TMBR: April 2026]] are currently work in progress.

This Year in Beaver Research (TYBR) is a yearly summary of Busy Beaver research progress. Its first edition, [[TYBR: 2025]] is currently work in progress.
==Notes==
<references />

BusyBeaverWiki - User contributions [en]

Main Page