Champions: Difference between revisions

Revision as of 13:58, 2 September 2024

Busy Beaver Champions are the current record holding 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 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. Take also note that the $f_{x}(n)$ used in the lowerbounds represent the Fast Growing Hierarchy.


	Runtime	Champions	Comment
BB(2)	$6$	`1RB1LB_1LA1RZ` (bbch) `1RB0LB_1LA1RZ` (bbch) `1RB1RZ_1LB1LA` (bbch) `1RB1RZ_0LB1LA` (bbch) `0RB1RZ_1LA1RB` (bbch)	Discovered and proven by hand by Tibor Radó
BB(3)	$21$	`1RB1RZ_1LB0RC_1LC1LA` (bbch)	Proven by Shen Lin
BB(4)	$107$	`1RB1LB_1LA0LC_1RZ1LD_1RD0RA` (bbch)	Discovered and proven by Allen Brady
BB(5)	$47,176,870$	`1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA` (bbch)	Discovered by Heiner Marxen & Jürgen Buntrock in 1989 Proven by bbchallenge.org in 2024
BB(6)	$>10\uparrow \uparrow 15$	`1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE` (bbch)	Discovered by Pavel Kropitz in 2022
BB(7)
BB(8)	$>2\uparrow ^{5}4>f_{6}(2)$	`1RH1RF_0LC0LH_0RD1LC_0RE1RA_1RB1RE_1RZ1RG_1RF0RE_1LB1LH` (bbch)	Discovered by Racheline in 2024
BB(9)
BB(10)	$>f_{\omega }^{2}(25)$	`1RB1RA_0LC0LF_0RD1LC_1RA1RG_1RZ0RA_1LB1LF_1LH1RE_0LI1LH_0LF0LJ_1LH0LJ` (bbch)	Discovered by Racheline in 2024
BB(11)	$>f_{\omega }^{2}(2\uparrow \uparrow 12)>f_{\omega }^{2}(f_{3}(9))$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RZ0LI_0LD1LE` (bbch)	Discovered by Racheline in 2024
BB(12)	$>f_{\omega }^{4}(2\uparrow \uparrow \uparrow 4-3)>f_{\omega }^{4}(f_{4}(2))$	`0LJ0RF_1LH1RC_0LD0LG_0RE1LD_1RF1RA_1RB1RF_1LC1LG_1LL1LI_1LK0LH_1RH1LJ_1RZ1LA_1RF1LL` (bbch)	Discovered by Racheline in 2024
BB(13)
BB(14)	$>f_{\omega +1}(65536)>g_{64}$	`1LH1LA_1LI1RG_0RD1LC_0RF1RE_1LJ0RF_1RB1RF_0LC1LH_0LC0LA_1LK1LJ_1RL0LI_0LL1LE_1LM1RZ_0LN1LF_0LJ---` (bbch)	Discovered by Racheline in 2024
BB(15)
BB(16)	$>f_{\omega +1}(2\uparrow \uparrow \uparrow \uparrow 2\uparrow \uparrow \uparrow \uparrow 9)$		Designed by Daniel Nagaj in 2021^[1]
BB(20)	$>f_{\omega +2}^{2}(21)$		Discovered by Racheline in 2024
BB(21)	$>f_{\omega ^{2}}^{2}(4\uparrow \uparrow 341)$		Discovered by Racheline in 2024
BB(51)	$>f_{\epsilon _{0}+1}(8)$		Designed by Racheline in 2024

3-Symbol TMs


	Runtime	Champions
BB(2,3)	$38$	`1RB2LB1RZ_2LA2RB1LB` (bbch)
BB(3,3)	$>10^{17}$	`0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC` (bbch)
BB(4,3)	$>10^{14072}$	`1RB1RZ2RC_2LC2RD0LC_1RA2RB0LB_1LB0LD2RC` (bbch)

4-Symbol TMs


	Runtime	Champions	Comment
BB(2,4)	$3,932,964$	`1RB2LA1RA1RA_1LB1LA3RB1RZ` (bbch)
BB(3,4)	$>2\uparrow ^{15}5$	`1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC` (bbch)

5-Symbol TMs


	Runtime	Champions	Comment
BB(2,5)	$>10^{10^{10^{3314360}}}$	`1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ` (bbch)
BB(3,5)	$>f_{\omega }(2\uparrow ^{15}5)>f_{\omega }^{2}(15)$	`1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC` (bbch)

References

↑ Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html

[1] Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html

[1]

@@ Line 11: / Line 11: @@
 |-
 |[[BB(2)]]
-|6
+|<math> 6 </math>
 |{{TM|1RB1LB_1LA1RZ|halt}} {{TM|1RB0LB_1LA1RZ|halt}} {{TM|1RB1RZ_1LB1LA|halt}} {{TM|1RB1RZ_0LB1LA|halt}} {{TM|0RB1RZ_1LA1RB|halt}}
 |Discovered and proven by hand by Tibor Radó
 |-
 |[[BB(3)]]
-|21
+|<math> 21 </math>
 |{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}}
 |Proven by Shen Lin
 |-
 |[[BB(4)]]
-|107
+|<math> 107 </math>
 |{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}}
 |Discovered and proven by Allen Brady
 |-
 |[[BB(5)]]
-|47,176,870
+|<math> 47,176,870 </math>
 |{{TM|1RB1LC_1RC1RB_1RD0LE_1LA1LD_1RZ0LA|halt}}
 |Discovered by Heiner Marxen & Jürgen Buntrock in 1989
@@ Line 32: / Line 32: @@
 |-
 |[[BB(6)]]
-|<math>> 10 \uparrow\uparrow 15</math>
+|<math> > 10 \uparrow\uparrow 15 </math>
 |{{TM|1RB0LD_1RC0RF_1LC1LA_0LE1RZ_1LF0RB_0RC0RE|halt}}
 |Discovered by Pavel Kropitz in 2022
@@ Line 85: / Line 85: @@
 |
 |Designed by  Daniel Nagaj in 2021<ref>Shawn Ligocki. 2022. "BB(16) > Graham's Number". https://www.sligocki.com/2022/07/11/bb-16-graham.html</ref>
+|-
+|BB(20)
+|<math> > f_{\omega + 2}^2(21) </math>
+|
+|Discovered by Racheline in 2024
+|-
+|BB(21)
+|<math> > f_{\omega^2}^2(4 \uparrow\uparrow 341) </math>
+|
+|Discovered by Racheline in 2024
 |-
 |BB(51)
 |<math> > f_{\epsilon_0 + 1}(8) </math>
 |
-|Discovered by Racheline in 2024
+|Designed by Racheline in 2024
 |}
@@ Line 102: / Line 112: @@
 |-
 |[[BB(2,3)]]
-|38
+|<math> 38 </math>
 |{{TM|1RB2LB1RZ_2LA2RB1LB|halt}}
 |
 |-
 |[[BB(3,3)]]
-|<math> > 10^{17}</math>
+|<math> > 10^{17} </math>
 |{{TM|0RB2LA1RA_1LA2RB1RC_1RZ1LB1LC|halt}}
 |-
@@ Line 125: / Line 135: @@
 |-
 |BB(2,4)
-|<math>\geq3,932,964</math>
+|<math> 3,932,964 </math>
-|
+|{{TM|1RB2LA1RA1RA_1LB1LA3RB1RZ|halt}}
 |
 |-
 |BB(3,4)
-|<math>>2\uparrow^{15}5</math>
+|<math> > 2 \uparrow^{15} 5 </math>
-|
+|{{TM|1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC|halt}}
 |
 |}
@@ Line 144: / Line 154: @@
 |-
 |BB(2,5)
-|<math>>10^{10^{10^{3314360}}}</math>
+|<math> > 10^{10^{10^{3314360}}} </math>
+|{{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ|halt}}
 |
+|-
+|BB(3,5)
+|<math> > f_\omega(2 \uparrow^{15} 5) > f_\omega^2(15) </math>
+|{{TM|1RB3LB4LC2RA4LB_2LC3RB1LC2RA1RZ_3RB1LB3LC2RC4LC|halt}}
 |
 |}