BusyBeaverWiki mediawiki https://wiki.bbchallenge.org/wiki/Main_Page MediaWiki 1.43.5 first-letter Media Special Talk User User talk BusyBeaverWiki BusyBeaverWiki talk File File talk MediaWiki MediaWiki talk Template Template talk Help Help talk Category Category talk Data Data talk Module Module talk 0 1 7196 7172 2026-04-17T02:34:26Z Sligocki 5 /* This Month in Beaver Research (TMBR) */ Update release 7196 wikitext text/x-wiki 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: March 2026]] * [[TMBR: February 2026]] * [[TMBR: January 2026]] [[TMBR: April 2026]] is currently a 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 /> 3daja4w3dfp5lkjrlygosbmmqb95ac8