BusyBeaverWiki - User contributions [en]

Main Page

2026-11-05T06:04:00Z

JackzNkk06:

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalized 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 [[wikipedia:Computability|computable]], but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values (up to 7 states and symbols)<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
!state→ symbol↓ !!2 !!3 !!4 !!5 !!6 !!7
|-
!2
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
|-
!3
| [[BB(2,3)]] = 38
| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
| style="background: #ddc290;" |
| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
| style="background: #ddc290;" |
|-
!4
| [[BB(2,4)]] = 3,932,964
| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" |
|-
!5
| style="background: orange;" title="Cryptids: Hydra and Bonus Cryptid" | [[BB(2,5)]] > <math>10^{10^{10^{3\,314\,360}}}</math>
| style="background: #ddc290;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: yellow;" | BB(4,5) > <math> f_{\omega+1}(27\,041)</math>
| style="background: yellow;" |BB(5,5) > <math>f_{\omega+1}(f_\omega^4(6))</math>
| style="background: yellow;" | BB(6,5) > <math>f_{\omega+3}(11)</math>
| style="background: yellow;" |BB(7,5) > <math>f_{\omega+3}^2(10)</math>
|-
!6
| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(63)</math>
|-
!7
| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
| style="background: yellow;" | BB(4,7) > <math> f_{\omega+2}(124)</math>
| style="background: yellow;" |
| style="background: yellow;" |
| style="background: yellow;" |
|}

'''Table key:'''

* Orange cell: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
* Tan cell: a Cryptid is known using fewer states or symbols than this class.
* Yellow cell: the Busy Beaver number is known to be more than [[Graham's number]].
* Blank cell: no known champion that surpasses a champion with fewer states or symbols by a non-trivial amount.

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:

* Formalizing 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|Accelerated simulator]]s to simulate halting machines faster
* Writing papers and giving talks about the Busy Beaver function, see [[Papers & Talks]]
* Exploring different [[:Category:Functions|Busy Beaver-style functions]] built from different systems of computation

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: May 2026]]
* [[TMBR: April 2026]]
* [[TMBR: March 2026]]

[[TMBR: June 2026]], [[TMBR: July 2026]], [[TMBR: August 2026]], [[TMBR: September 2026]], [[TMBR: October 2026]], and [[TMBR: November 2026]] are currently works in progress.

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

==Notes==
<references />

Main Page

2026-11-05T06:01:01Z

JackzNkk06:

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalized 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 [[wikipedia:Computability|computable]], but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values (up to 7 states and symbols)<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
!state symbol !!2 !!3 !!4 !!5 !!6 !!7
|-
!2
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
|-
!3
| [[BB(2,3)]] = 38
| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
| style="background: #ddc290;" |
| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
| style="background: #ddc290;" |
|-
!4
| [[BB(2,4)]] = 3,932,964
| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" |
|-
!5
| style="background: orange;" title="Cryptids: Hydra and Bonus Cryptid" | [[BB(2,5)]] > <math>10^{10^{10^{3\,314\,360}}}</math>
| style="background: #ddc290;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: yellow;" | BB(4,5) > <math> f_{\omega+1}(27\,041)</math>
| style="background: yellow;" |BB(5,5) > <math>f_{\omega+1}(f_\omega^4(6))</math>
| style="background: yellow;" | BB(6,5) > <math>f_{\omega+3}(11)</math>
| style="background: yellow;" |BB(7,5) > <math>f_{\omega+3}^2(10)</math>
|-
!6
| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(63)</math>
|-
!7
| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
| style="background: yellow;" | BB(4,7) > <math> f_{\omega+2}(124)</math>
| style="background: yellow;" |
| style="background: yellow;" |
| style="background: yellow;" |
|}

'''Table key:'''

* Orange cell: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
* Tan cell: a Cryptid is known using fewer states or symbols than this class.
* Yellow cell: the Busy Beaver number is known to be more than [[Graham's number]].
* Blank cell: no known champion that surpasses a champion with fewer states or symbols by a non-trivial amount.

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:

* Formalizing 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|Accelerated simulator]]s to simulate halting machines faster
* Writing papers and giving talks about the Busy Beaver function, see [[Papers & Talks]]
* Exploring different [[:Category:Functions|Busy Beaver-style functions]] built from different systems of computation

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: May 2026]]
* [[TMBR: April 2026]]
* [[TMBR: March 2026]]

[[TMBR: June 2026]], [[TMBR: July 2026]], [[TMBR: August 2026]], [[TMBR: September 2026]], [[TMBR: October 2026]], and [[TMBR: November 2026]] are currently works in progress.

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

==Notes==
<references />

Main Page

2026-11-05T06:00:44Z

JackzNkk06:

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalized 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 [[wikipedia:Computability|computable]], but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values (up to 7 states and symbols)<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
!state\n symbol !!2 !!3 !!4 !!5 !!6 !!7
|-
!2
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
|-
!3
| [[BB(2,3)]] = 38
| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
| style="background: #ddc290;" |
| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
| style="background: #ddc290;" |
|-
!4
| [[BB(2,4)]] = 3,932,964
| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" |
|-
!5
| style="background: orange;" title="Cryptids: Hydra and Bonus Cryptid" | [[BB(2,5)]] > <math>10^{10^{10^{3\,314\,360}}}</math>
| style="background: #ddc290;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: yellow;" | BB(4,5) > <math> f_{\omega+1}(27\,041)</math>
| style="background: yellow;" |BB(5,5) > <math>f_{\omega+1}(f_\omega^4(6))</math>
| style="background: yellow;" | BB(6,5) > <math>f_{\omega+3}(11)</math>
| style="background: yellow;" |BB(7,5) > <math>f_{\omega+3}^2(10)</math>
|-
!6
| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(63)</math>
|-
!7
| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
| style="background: yellow;" | BB(4,7) > <math> f_{\omega+2}(124)</math>
| style="background: yellow;" |
| style="background: yellow;" |
| style="background: yellow;" |
|}

'''Table key:'''

* Orange cell: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
* Tan cell: a Cryptid is known using fewer states or symbols than this class.
* Yellow cell: the Busy Beaver number is known to be more than [[Graham's number]].
* Blank cell: no known champion that surpasses a champion with fewer states or symbols by a non-trivial amount.

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:

* Formalizing 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|Accelerated simulator]]s to simulate halting machines faster
* Writing papers and giving talks about the Busy Beaver function, see [[Papers & Talks]]
* Exploring different [[:Category:Functions|Busy Beaver-style functions]] built from different systems of computation

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: May 2026]]
* [[TMBR: April 2026]]
* [[TMBR: March 2026]]

[[TMBR: June 2026]], [[TMBR: July 2026]], [[TMBR: August 2026]], [[TMBR: September 2026]], [[TMBR: October 2026]], and [[TMBR: November 2026]] are currently works in progress.

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

==Notes==
<references />

Main Page

2026-11-05T06:00:25Z

JackzNkk06:

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalized 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 [[wikipedia:Computability|computable]], but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values (up to 7 states and symbols)<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
!state

symbol !!2 !!3 !!4 !!5 !!6 !!7
|-
!2
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
|-
!3
| [[BB(2,3)]] = 38
| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
| style="background: #ddc290;" |
| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
| style="background: #ddc290;" |
|-
!4
| [[BB(2,4)]] = 3,932,964
| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" |
|-
!5
| style="background: orange;" title="Cryptids: Hydra and Bonus Cryptid" | [[BB(2,5)]] > <math>10^{10^{10^{3\,314\,360}}}</math>
| style="background: #ddc290;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: yellow;" | BB(4,5) > <math> f_{\omega+1}(27\,041)</math>
| style="background: yellow;" |BB(5,5) > <math>f_{\omega+1}(f_\omega^4(6))</math>
| style="background: yellow;" | BB(6,5) > <math>f_{\omega+3}(11)</math>
| style="background: yellow;" |BB(7,5) > <math>f_{\omega+3}^2(10)</math>
|-
!6
| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(63)</math>
|-
!7
| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
| style="background: yellow;" | BB(4,7) > <math> f_{\omega+2}(124)</math>
| style="background: yellow;" |
| style="background: yellow;" |
| style="background: yellow;" |
|}

'''Table key:'''

* Orange cell: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
* Tan cell: a Cryptid is known using fewer states or symbols than this class.
* Yellow cell: the Busy Beaver number is known to be more than [[Graham's number]].
* Blank cell: no known champion that surpasses a champion with fewer states or symbols by a non-trivial amount.

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:

* Formalizing 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|Accelerated simulator]]s to simulate halting machines faster
* Writing papers and giving talks about the Busy Beaver function, see [[Papers & Talks]]
* Exploring different [[:Category:Functions|Busy Beaver-style functions]] built from different systems of computation

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: May 2026]]
* [[TMBR: April 2026]]
* [[TMBR: March 2026]]

[[TMBR: June 2026]], [[TMBR: July 2026]], [[TMBR: August 2026]], [[TMBR: September 2026]], [[TMBR: October 2026]], and [[TMBR: November 2026]] are currently works in progress.

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

==Notes==
<references />

Main Page

2026-11-05T06:00:02Z

JackzNkk06:

The [[Busy Beaver function]] BB (called ''S'' originally) was introduced by [[Tibor Radó]] in 1962 for 2-symbol [[Turing machines]] and later generalized 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 [[wikipedia:Computability|computable]], but a few of its values are known:

{| class="wikitable"
|+ Small busy beaver values (up to 7 states and symbols)<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
!state/symbol !!2 !!3 !!4 !!5 !!6 !!7
|-
!2
| [[BB(2)]] = 6
| [[BB(3)]] = 21
| [[BB(4)]] = 107
| [[BB(5)]] = 47,176,870
| style="background: orange;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
|-
!3
| [[BB(2,3)]] = 38
| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
| style="background: #ddc290;" |
| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
| style="background: #ddc290;" |
|-
!4
| [[BB(2,4)]] = 3,932,964
| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
| style="background: yellow;" |
|-
!5
| style="background: orange;" title="Cryptids: Hydra and Bonus Cryptid" | [[BB(2,5)]] > <math>10^{10^{10^{3\,314\,360}}}</math>
| style="background: #ddc290;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
| style="background: yellow;" | BB(4,5) > <math> f_{\omega+1}(27\,041)</math>
| style="background: yellow;" |BB(5,5) > <math>f_{\omega+1}(f_\omega^4(6))</math>
| style="background: yellow;" | BB(6,5) > <math>f_{\omega+3}(11)</math>
| style="background: yellow;" |BB(7,5) > <math>f_{\omega+3}^2(10)</math>
|-
!6
| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(63)</math>
|-
!7
| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
| style="background: yellow;" | BB(4,7) > <math> f_{\omega+2}(124)</math>
| style="background: yellow;" |
| style="background: yellow;" |
| style="background: yellow;" |
|}

'''Table key:'''

* Orange cell: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
* Tan cell: a Cryptid is known using fewer states or symbols than this class.
* Yellow cell: the Busy Beaver number is known to be more than [[Graham's number]].
* Blank cell: no known champion that surpasses a champion with fewer states or symbols by a non-trivial amount.

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:

* Formalizing 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|Accelerated simulator]]s to simulate halting machines faster
* Writing papers and giving talks about the Busy Beaver function, see [[Papers & Talks]]
* Exploring different [[:Category:Functions|Busy Beaver-style functions]] built from different systems of computation

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: May 2026]]
* [[TMBR: April 2026]]
* [[TMBR: March 2026]]

[[TMBR: June 2026]], [[TMBR: July 2026]], [[TMBR: August 2026]], [[TMBR: September 2026]], [[TMBR: October 2026]], and [[TMBR: November 2026]] are currently works in progress.

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

==Notes==
<references />