Main Page: Difference between revisions

Latest revision as of 15:40, 7 November 2026

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:^[1]^[2]

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:

Small busy beaver values (up to 7 states and symbols)^[3]
	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	BB(6) > $10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 8$	BB(7) > $3 ↑^{20} 3$
3-symbol	BB(2,3) = 38	BB(3,3) $\geq$ 119,112,334,170,342,541	BB(4,3) > $10 ↑^{4} 4$		BB(6,3) > $f_{ω}^{2} (10 ↑ ↑ ↑ 6)$
4-symbol	BB(2,4) = 3,932,964	BB(3,4) > $2 ↑^{15} 5$	BB(4,4) > $2 ↑^{509} 3$	BB(5,4) > $f_{ω}^{2} (10 ↑^{4} 10 ↑ ↑ 65 533)$	BB(6,4) > $f_{ω + 1} (10 ↑ ↑ 65 533)$	BB(7,4) > $f_{ω + 3} (21)$
5-symbol	BB(2,5) > $1 0^{1 0^{1 0^{3 314 360}}}$	BB(3,5) > $f_{ω} (2 ↑^{15} 5)$	BB(4,5) > $f_{ω + 1} (27 041)$	BB(5,5) > $f_{ω + 1} (f_{ω}^{4} (6))$	BB(6,5) > $f_{ω + 3} (11)$	BB(7,5) > $f_{ω + 3}^{2} (10)$
6-symbol	BB(2,6) > $10 ↑ ↑ 10 ↑ ↑ 1 0^{1 0^{115}}$	BB(3,6) > $f_{ω}^{3} (15)$	BB(4,6) > $f_{ω + 2} (29)$	BB(5,6) > $f_{ω + 3} (31)$	BB(6,6) > $f_{ω \times 2} (89)$	BB(7,6) > $f_{ω^{2}} (110)$
7-symbol	BB(2,7) > $10 ↑ ↑ 10 ↑ ↑ 10 ↑ ↑ 155$	BB(3,7) > $f_{ω + 1} (117)$	BB(4,7) > $f_{ω + 3} (34)$

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 Rocq)
Maintaining Holdouts lists for small busy beaver values
Proving the behavior of Individual machines
Finding Cryptids (mathematically-hard machines)
Searching for new Champions
Building Accelerated simulators to simulate halting machines faster
Writing papers and giving talks about the Busy Beaver function, see Papers & Talks
Exploring different Busy Beaver-style functions built from different systems of computation

In June 2024, bbchallenge achieved a significant milestone by proving in 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.^[4]

This Month in Beaver Research (TMBR)

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: 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

↑ 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
↑ 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.
↑ P. Michel, "Historical survey of Busy Beavers".
↑ 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

[1] 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

[2] 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.

[3] P. Michel, "Historical survey of Busy Beavers".

[4] 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

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-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>
+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"
@@ Line 6: / Line 6: @@
 |}
-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:
+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<ref>P. Michel, "[https://bbchallenge.org/~pascal.michel/ha.html Historical survey of Busy Beavers]".</ref>
+|+ 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>
-! !!2-state!!3-state !!4-state!!5-state!!6-state
+! !!2-state !!3-state !!4-state !!5-state !!6-state !!7-state
-!7-state
+|-
-|-
+!2-symbol
-! 2-symbol
+| [[BB(2)]] = 6
-| [[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;" title="Cryptids: Antihydra and some other cryptids" | [[BB(6)]] > <math>10 \uparrow\uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 8</math>
-| style="background: orange;" | [[BB(7)]] > <math>2 \uparrow^{11} 2 \uparrow^{11} 3</math>
+| style="background: #ddc290;" | [[BB(7)]] > <math>3 \uparrow^{20} 3</math>
 |-
-! 3-symbol
+!3-symbol
 | [[BB(2,3)]] = 38
-| style="background: orange;" | [[BB(3,3)]] > <math>10^{17}</math>
+| style="background: orange;" title="Cryptid: Bigfoot" | [[BB(3,3)]] <math>\ge</math> 119,112,334,170,342,541
-| style="background: #ffe4b2;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
+| style="background: #ddc290;" | [[BB(4,3)]] > <math>10 \uparrow^{4} 4</math>
-| style="background: #ffe4b2;" |
+| style="background: #ddc290;" |
-| style="background: #ffe4b2;" |
+| style="background: #ddc290;" | BB(6,3) > <math> f_\omega^2(10\uparrow\uparrow\uparrow 6)</math>
-| style="background: #ffe4b2;" |
+| style="background: #ddc290;" |
 |-
-! 4-symbol
+!4-symbol
 | [[BB(2,4)]] = 3,932,964
-| style="background: #ffe4b2;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
+| style="background: #ddc290;" | [[BB(3,4)]] > <math>2 \uparrow^{15} 5</math>
-| style="background: #ffe4b2;" |
+| style="background: #ddc290;" | [[BB(4,4)]] > <math>2 \uparrow^{509} 3</math>
-| style="background: #ffe4b2;" |
+| style="background: #ddc290;" | BB(5,4) > <math>f_\omega^2(10\uparrow^4 10\uparrow\uparrow 65\,533)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(6,4) > <math> f_{\omega+1}(10\uparrow\uparrow 65\,533)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" |BB(7,4) > <math> f_{\omega+3}(21)</math>
+|-
+!5-symbol
+| 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>
 |-
-! 5-symbol
+!6-symbol
-| style="background: orange;" | [[BB(2,5)]] > <math>10\uparrow\uparrow 4</math>
+| style="background: #ddc290;" | [[BB(2,6)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
-| style="background: #ffe4b2;" | [[BB(3,5)]] > <math> f_\omega(2 \uparrow^{15} 5)</math>
+| style="background: #ddc290;" | BB(3,6) > <math> f_\omega^3(15)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(4,6) > <math> f_{\omega+2}(29)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(5,6) > <math> f_{\omega+3}(31)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(6,6) > <math> f_{\omega \times 2}(89)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(7,6) > <math> f_{\omega^2}(110)</math>
 |-
-! 6-symbol
+!7-symbol
-| style="background: #ffe4b2;" | [[BB(2,6)]] > <math>10 \uparrow\uparrow\uparrow 3</math>
+| style="background: #ddc290;" | [[BB(2,7)]] > <math>10 \uparrow \uparrow 10 \uparrow\uparrow 10 \uparrow\uparrow 155</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(3,7) > <math> f_{\omega+1}(117)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" | BB(4,7) > <math>f_{\omega+3}(34)</math>
-| style="background: #ffe4b2;" |
+| style="background: yellow;" |
-| style="background: #ffe4b2;" |
+| style="background: yellow;" |
-| style="background: #ffe4b2;" |
+| style="background: yellow;" |
 |}
-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 less states or symbols.
+'''Table key:'''
+* <span style="background: orange">Orange cell</span>: smallest known [[Cryptid]] (a mathematically-hard machine) is in this class
+* <span style="background: #ddc290">Tan cell</span>: a Cryptid is known using fewer states or symbols than this class.
+* <span style="background: yellow">Yellow cell</span>: 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.
 -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:
+[[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])
+* 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]]s to simulate halting machines faster
+* Building [[Accelerated Simulator|Accelerated simulator]]s to simulate halting machines faster
-* Writing papers and giving talks about busy beaver, see [[Papers & Talks]]
+* 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.
@@ Line 75: / Line 88: @@
 [[: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: November 2025|TMBR November 2025]]
+* [[TMBR: April 2026]]
-* [[TMBR: October 2025|TMBR October 2025]]
+* [[TMBR: March 2026]]
-* [[TMBR: September 2025|TMBR September 2025]]
+* [[TMBR: February 2026]]
+[[TMBR: May 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.
-[[TMBR: December 2025|TMBR December 2025]] is 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 a work in progress.
 ==Notes==
 <references />

Main Page: Difference between revisions

Latest revision as of 15:40, 7 November 2026

About bbchallenge

This Month in Beaver Research (TMBR)

Notes

Navigation menu

Search