Champions: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
(Take also note --> Also take note)
 
(34 intermediate revisions by 11 users not shown)
Line 1: Line 1:
Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] who maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].
Busy Beaver '''Champions''' are the current record holding [[Turing machine|Turing machines]] which maximize a [[Busy Beaver function]]. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for [https://bbchallenge.org/~pascal.michel/bbc Busy Beaver champions] and the [https://bbchallenge.org/~pascal.michel/ha History of Previous Champions].


== 2-Symbol TMs ==
== 2-Symbol TMs ==
Rows are blank if no champion has been found which surpasses a smaller size problem. Take also note that the <math> f_{x}(n) </math> used in the lowerbounds represent the [https://googology.fandom.com/wiki/Fast-growing_hierarchy Fast Growing Hierarchy]. Note that most champions above 6 states are self-reported and have not been independently verified.
Rows are blank if no champion has been found which surpasses a smaller size problem. Also take note that the <math> f_{x}(n) </math> used in the lower bounds represent the [[Fast-Growing Hierarchy]]. Note that most champions above 6 states are self-reported and have not been independently verified.


{| class="wikitable"
{| class="wikitable"
Line 11: Line 11:
!Discovered By
!Discovered By
!Verification
!Verification
!
|-
|-
|[[BB(2)]]
|[[BB(2)]]
|<math> 6 </math>
|<math>6</math>
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
|Tibor Radó
|Tibor Radó
Line 20: Line 19:
|-
|-
|[[BB(3)]]
|[[BB(3)]]
|<math> 21 </math>
|<math>21</math>
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
|Proven by Shen Lin
|Proven by Shen Lin
Line 26: Line 25:
|-
|-
|[[BB(4)]]
|[[BB(4)]]
|<math> 107 </math>
|<math>107</math>
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
|Allen Brady
|Allen Brady
Line 32: Line 31:
|-
|-
|[[BB(5)]]
|[[BB(5)]]
|<math> 47\,176\,870 </math>
|<math>47\,176\,870</math>
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
|Heiner Marxen & Jürgen Buntrock in 1989
|Heiner Marxen & Jürgen Buntrock in 1989
Line 38: Line 37:
|-
|-
|[[BB(6)]]
|[[BB(6)]]
|<math> > 10 \uparrow\uparrow 15 </math>
|<math>> 2\uparrow\uparrow\uparrow 5</math>
|{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
|{{TM|1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE|halt}}
|Pavel Kropitz in 2022
|mxdys in 2025
|[https://www.sligocki.com/2022/06/21/bb-6-2-t15.html Analysis by Shawn Ligocki]
|See mxdys's analysis on the TM page
|-
|-
|[[BB(7)]]
|[[BB(7)]]
|<math>> 2 \uparrow^{11} 2 \uparrow^{11} 3</math>
|{{TM|1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF|halt}}
|[https://discord.com/channels/960643023006490684/1369339127652159509/1370678203395604562 Pavel Kropitz in 2025]
|Analyzed by Shawn Ligocki (see TM page)
|-
|[[BB(8)]]
|
|
|
|
|
|
|
|-
|BB(8)
|<math> > 2 \uparrow^5 4 > f_6(2) </math>
|{{TM|1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH|halt}}
|Racheline in 2024
|
|
|-
|-
|BB(9)
|BB(9)
|<math> > f_\omega(f_9(2)) </math>
|<math>> f_\omega(f_9(2))</math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH|halt}}
|Jacobzheng in 2024
|Jacobzheng in 2024
Line 62: Line 61:
|-
|-
|BB(10)
|BB(10)
|<math> > f_\omega^2(25) </math>
|<math>> f_\omega^2(25)</math>
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|{{TM|1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ|halt}}
|Racheline in 2024
|Racheline in 2024
Line 68: Line 67:
|-
|-
|BB(11)
|BB(11)
|<math> > f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9)) </math>
|<math>> f_\omega^2(2 \uparrow\uparrow 12) > f_\omega^2(f_3(9))</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE|halt}}
|Racheline in 2024
|Racheline in 2024
Line 74: Line 73:
|-
|-
|BB(12)
|BB(12)
|<math> > f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2)) </math>
|<math>> f_\omega^4(2 \uparrow\uparrow\uparrow 4-3) > f_\omega^4(f_4(2))</math>
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|{{TM|0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL|halt}}
|Racheline in 2024
|Racheline in 2024
Line 86: Line 85:
|-
|-
|BB(14)
|BB(14)
|<math> > f_{\omega + 1}(65\,536) > g_{64} </math>
|<math>> f_{\omega + 1}(65\,536) > g_{64}</math>
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|{{TM|1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---|halt}}
|[https://discord.com/channels/960643023006490684/960643023530762341/1274366178529120287 Racheline in 2024]
|[https://discord.com/channels/960643023006490684/960643023530762341/1274366178529120287 Racheline in 2024]
Line 92: Line 91:
|-
|-
|BB(15)
|BB(15)
|
|<math>> f_{\omega + 1}(f_\omega(10^{57}))</math>
|
|{{TM|0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_1RZ0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN|halt}}
|
|Jacobzheng in 2025
|
|
|-
|-
|BB(16)
|BB(16)
|<math> > f_{\omega + 1}(2 \uparrow\uparrow\uparrow\uparrow 2 \uparrow\uparrow\uparrow\uparrow 9) </math>
|<math>> f_{\omega + 1}^2(10^{10^{57}})</math>
|[[User:Jacobzheng/BB(16)]]
|Jacobzheng in 2025
|
|
|Daniel Nagaj in 2021
|[https://www.sligocki.com/2022/07/11/bb-16-graham.html Analysis by Shawn Ligocki]
|-
|-
|BB(17)
|BB(17)
|<math> > f_{\omega + 1}(f_\omega(60)) </math>
|
|[[User:Jacobzheng/BB(17)]]
|
|Jacobzheng in 2024
|
|
|
|-
|-
|BB(18)
|BB(18)
|<math> > f_{\omega + 1}(f_\omega^2(60)) </math>
|<math>> f_{\omega + 2}(f_{\omega + 1}^3(f_{\omega}^2(60)))</math>
|[[User:Jacobzheng/BB(18)]]
|[[User:Jacobzheng/BB(18)]]
|Jacobzheng in 2024
|Jacobzheng in 2025
|
|
|-
|-
|BB(19)
|BB(19)
|<math> > f_{\omega + 1}^3(f_\omega(60)) </math>
|
|[[User:Jacobzheng/BB(19)]]
|
|Jacobzheng in 2024
|
|
|
|-
|-
|BB(20)
|BB(20)
|<math> > f_{\omega + 2}^2(21) </math>
|<math>> f_{\omega + 2}^2(21)</math>
|
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274414683331366924 Racheline in 2024]
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274414683331366924 Racheline in 2024]
Line 128: Line 127:
|-
|-
|BB(21)
|BB(21)
|<math> > f_{\omega^2}^2(4 \uparrow\uparrow 341) </math>
|<math>> f_{\omega^2}^2(4 \uparrow\uparrow 341)</math>
|
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274471360206344213 Racheline in 2024]
|[https://discord.com/channels/960643023006490684/1026577255754903572/1274471360206344213 Racheline in 2024]
|
|-
|BB(40)
|<math>> f_{\omega^\omega}(75\,500)</math>
|[[User:Jacobzheng/BB(40)]]
|Jacobzheng in 2024
|
|
|-
|-
|BB(41)
|BB(41)
|<math> > f_{\omega^\omega}^4(32) </math>
|<math>> f_{\omega^\omega}^4(32)</math>
|[[User:Jacobzheng/BB(41)]]
|[[User:Jacobzheng/BB(41)]]
|Jacobzheng in 2024
|Jacobzheng in 2024
Line 140: Line 145:
|-
|-
|BB(51)
|BB(51)
|<math> > f_{\varepsilon_0 + 1}(8) </math>
|<math>> f_{\varepsilon_0 + 1}(8)</math>
|
|
|[https://discord.com/channels/960643023006490684/1026577255754903572/1276881449685094495 Racheline in 2024]
|[https://discord.com/channels/960643023006490684/1026577255754903572/1276881449685094495 Racheline in 2024]
Line 155: Line 160:
!Discovered By
!Discovered By
!Verification
!Verification
!
|-
|-
|[[BB(2,3)]]
|[[BB(2,3)]]
|<math> 38 </math>
|<math>38</math>
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
|
|Allen Brady in 1988
|Direct Simulation
|-
|-
|[[BB(3,3)]]
|[[BB(3,3)]]
|<math> > 10^{17} </math>
|<math>> 10^{17}</math>
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
|
|Terry & Shawn Ligocki in 2007
|[https://bbchallenge.org/~pascal.michel/beh#tm33h Analysis by Pascal Michel]
|-
|-
|[[BB(4,3)]]
|[[BB(4,3)]]
|<math> > 10^{14072} </math>
|<math>> 2 \uparrow\uparrow\uparrow 2^{2^{32}}</math>
|{{TM|1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC|halt}}
|{{TM|0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD|halt}}
|Pavel Kropitz in 2024
|
|
|}
|}
Line 181: Line 188:
!Discovered By
!Discovered By
!Verification
!Verification
!
|-
|-
|BB(2,4)
|[[BB(2,4)]]
|<math> 3\,932\,964 </math>
|<math>3\,932\,964</math>
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
|
|Terry & Shawn Ligocki in 2005
|Pascal Michel, Heiner Marxen, Allen Brady
|-
|-
|BB(3,4)
|[[BB(3,4)]]
|<math> > 2 \uparrow^{15} 5 </math>
|<math>> 2 \uparrow^{15} 5</math>
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
|
|Pavel Kropitz in 2024
|[https://www.sligocki.com/2024/05/22/bb-3-4-a14.html Analysis by Shawn Ligocki]
|}
|}


Line 201: Line 209:
!Discovered By
!Discovered By
!Verification
!Verification
!
|-
|-
|BB(2,5)
|[[BB(2,5)]]
|<math> > 10^{10^{10^{3\,314\,360}}} </math>
|<math>> 10^{10^{10^{3\,314\,360}}}</math>
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
|
|Daniel Yuan in 2024
|
|[https://discord.com/channels/960643023006490684/1259770421046411285/1379877629288644722 mxdys in Coq]
|-
|-
|BB(3,5)
|[[BB(3,5)]]
|<math> > f_\omega(2 \uparrow^{15} 5) > f_\omega^2(15) </math>
|<math>> f_\omega(2 \uparrow^{15} 5) > f_\omega^2(15)</math>
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
|
|Racheline in 2024
|
|
|}
|}


== References ==
== 6-Symbol TMs ==
<references />
{| class="wikitable"
!
!Runtime
!Champions
!Discovered By
!Verification
|-
|[[BB(2,6)]]
|<math>> 10 \uparrow\uparrow 10 \uparrow\uparrow 10^{10^{115}}</math>
|{{TM|1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA|halt}}
|Pavel Kropitz in 2023
|[https://www.sligocki.com/2023/05/20/bb-2-6-p3.html Analysis by Shawn Ligocki]
|}

Latest revision as of 20:31, 14 August 2025

Busy Beaver Champions are the current record holding Turing machines which maximize a Busy Beaver function. In this article we focus specifically on the longest running TMs. Some have been proven to be the longest running of all (and so are the ultimate champion) while others are only current champions and may be usurped in the future. For smaller domains, Pascal Michel's website is the canonical source for Busy Beaver champions and the History of Previous Champions.

2-Symbol TMs

Rows are blank if no champion has been found which surpasses a smaller size problem. Also take note that the used in the lower bounds represent the Fast-Growing Hierarchy. Note that most champions above 6 states are self-reported and have not been independently verified.

Runtime Champions Discovered By Verification
BB(2) 1RB1LB_1LA1RZ (bbch) 1RB0LB_1LA1RZ (bbch) 1RB1RZ_1LB1LA (bbch) 1RB1RZ_0LB1LA (bbch) 0RB1RZ_1LA1RB (bbch) Tibor Radó Direct Simulation
BB(3) 1RB1RZ_1LB0RC_1LC1LA (bbch) Proven by Shen Lin Direct Simulation
BB(4) 1RB1LB_1LA0LC_1RZ1LD_1RD0RA (bbch) Allen Brady Direct Simulation
BB(5) 1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA (bbch) Heiner Marxen & Jürgen Buntrock in 1989 Direct Simulation
BB(6) 1RB1RA_1RC1RZ_1LD0RF_1RA0LE_0LD1RC_1RA0RE (bbch) mxdys in 2025 See mxdys's analysis on the TM page
BB(7) 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch) Pavel Kropitz in 2025 Analyzed by Shawn Ligocki (see TM page)
BB(8)
BB(9) 1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_1LB0LH (bbch) Jacobzheng in 2024
BB(10) 1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ (bbch) Racheline in 2024
BB(11) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE (bbch) Racheline in 2024
BB(12) 0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL (bbch) Racheline in 2024
BB(13)
BB(14) 1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ--- (bbch) Racheline in 2024
BB(15) 0RH1LD_1RI0RC_1RB1LD_0LD1LE_1LF1RA_1RG0LE_1RB1RG_1RD1RA_0LN0RJ_1RZ0LK_0LK1LL_1RG1LM_0LL0LL_1LO1LN_0LG1LN (bbch) Jacobzheng in 2025
BB(16) User:Jacobzheng/BB(16) Jacobzheng in 2025
BB(17)
BB(18) User:Jacobzheng/BB(18) Jacobzheng in 2025
BB(19)
BB(20) Racheline in 2024
BB(21) Racheline in 2024
BB(40) User:Jacobzheng/BB(40) Jacobzheng in 2024
BB(41) User:Jacobzheng/BB(41) Jacobzheng in 2024
BB(51) Racheline in 2024

3-Symbol TMs

Runtime Champions Discovered By Verification
BB(2,3) 1RB2LB1RZ_2LA2RB1LB (bbch) Allen Brady in 1988 Direct Simulation
BB(3,3) 0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC (bbch) Terry & Shawn Ligocki in 2007 Analysis by Pascal Michel
BB(4,3) 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) Pavel Kropitz in 2024

4-Symbol TMs

Runtime Champions Discovered By Verification
BB(2,4) 1RB2LA1RA1RA_1LB1LA3RB1RZ (bbch) Terry & Shawn Ligocki in 2005 Pascal Michel, Heiner Marxen, Allen Brady
BB(3,4) 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch) Pavel Kropitz in 2024 Analysis by Shawn Ligocki

5-Symbol TMs

Runtime Champions Discovered By Verification
BB(2,5) 1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ (bbch) Daniel Yuan in 2024 mxdys in Coq
BB(3,5) 1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC (bbch) Racheline in 2024

6-Symbol TMs

Runtime Champions Discovered By Verification
BB(2,6) 1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch) Pavel Kropitz in 2023 Analysis by Shawn Ligocki
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=Champions&oldid=3141"