BB(2,6): Difference between revisions

Latest revision as of 20:01, 28 September 2025

The 2-state, 6-symbol Busy Beaver problem, BB(2,6), is unsolved. With cryptids like Hydra in the preceding domain BB(2,5), we know that we must solve a Collatz-like problem in order to solve BB(2,6).

The current BB(2,6) champion 1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch) was discovered by Pavel Kropitz in May 2023, proving the lower bound:

S(2,6)>\Sigma (2,6)>10\uparrow \uparrow 10\uparrow \uparrow 10^{10^{115}}>10\uparrow \uparrow \uparrow 3

Top Halters

The scores are given using Knuth's up-arrow notation with an extension to decimal tetration^[1]. The 20 highest known scoring machines are:


TM	Approximate sigma score	Discoverer
`1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA` (bbch)	10 ↑↑↑ 3	Pavel Kropitz
`1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ` (bbch)	10 ↑↑ 91.17	Pavel Kropitz
`1RB2LA1RA4LA5RA0LB_1LA3RA2RB1RZ3RB4LA` (bbch)	10 ↑↑ 70.27	Shawn Ligocki
`1RB2LB1RZ3LA2LA4RB_1LA3RB4RB1LB5LB0RA` (bbch)	10 ↑↑ 69.68	Shawn Ligocki
`1RB2LB0RA2RA5RA1LB_2LA4RB3LB2RB0RB1RZ` (bbch)	10 ↑↑ 54.90	Andrew Ducharme
`1RB3RB1LB5LA2LB1RZ_2LA3RA4RB2LB0LA4RB` (bbch)	10 ↑↑ 42.17	Andrew Ducharme
`1RB3LB0RB5RA1LB1RZ_2LB3LA4RA0RB0RA2LB` (bbch)	10 ↑↑ 40.07	Andrew Ducharme
`1RB3LB3RB4LA2LA4LA_2LA2RB1LB0RA5RA1RZ` (bbch)	10 ↑↑ 21.54	Shawn Ligocki
`1RB2LB3LA1RA0RA1RZ_1LA2RB1LB4RB5RA3LA` (bbch)	10 ↑↑ 20.58	Shawn Ligocki
`1RB0RA3RB0LB1RA2LA_2LA4LB1RA3LB5LB1RZ` (bbch)	10 ↑↑ 17.53	Shawn Ligocki
`1RB0RA3RB0LB5LA2LA_2LA4LB1RA3LB5LB1RZ` (bbch)	10 ↑↑ 17.53	Andrew Ducharme
`1RB3RA4LB5RA5LB4RA_2LA1RZ1RB2LA5LA0LA` (bbch)	10 ↑↑ 17.08	Andrew Ducharme
`1RB3RA4LA1LA0LA1RZ_2LA0LB1RA1LB5LB2RA` (bbch)	10 ↑↑ 15.44	Andrew Ducharme
`1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ2LA` (bbch)	10 ↑↑ 14.35	Andrew Ducharme
`1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ3RA` (bbch)	10 ↑↑ 14.17	Andrew Ducharme
`1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ1LA` (bbch)	10 ↑↑ 14.05	Andrew Ducharme
`1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ0RA` (bbch)	10 ↑↑ 13.69	Andrew Ducharme
`1RB3LA3RA4LB2LB0LA_2LA5LB2RB0RA0RA1RZ` (bbch)	10 ↑↑ 12.42	Andrew Ducharme
`1RB0LB4LA2RA2RB1LB_2LA4LA3LB5LA1RA1RZ` (bbch)	10 ↑↑ 11.70	Andrew Ducharme
`1RB2LA1RA1RA5LB1RZ_1LA4RB3RB4LB0RB0RA` (bbch)	10 ↑↑ 10.39	Andrew Ducharme

All decimal places are truncated.

Phase 1

The initial phase of enumeration and reduction of holdouts took place in December 2024 and was done by Terry Ligocki using the Ligockis' C++ and Python codes. The initial enumerations generated ~24B(illion) TMs of which ~2,278M were holdout TMs. This was reduced to ~22M holdout TMs (a 99.02% reduction). The details will be given in this table:

(done to reduce column size: $*^{1}$ = % Reduced, $*^{2}$ = Runtime (hours), $*^{3}$ = Decided, $*^{4}$ = Processed)

Done by	Holdout TMs		$*^{1}$	$*^{2}$	TMs/sec/core		Description	Data
Done by	Input	Output	$*^{1}$	$*^{2}$	$*^{3}$	$*^{4}$	Description	Data
---	---	---	---	---	---	---	---

Phase 2

Starting from Terry Ligocki's holdouts list of 22,302,296 TMs, additional filtering has been performed:

(done to reduce column size: $*^{1}$ = % Reduced, $*^{2}$ = Compute Time (core-hours), $*^{3}$ = Decided, $*^{4}$ = Processed)

Done by	Holdout TMs		$*^{1}$	$*^{2}$	TMs/sec/core		Description	Data
Done by	Input	Output	$*^{1}$	$*^{2}$	$*^{3}$	$*^{4}$	Description	Data
Terry Ligocki	22,302,296	20,246,662	9.2%	23.0	24.80	269.09	MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 6 run	Google Drive
Terry Ligocki	20,246,662	19,134,631	5.5%	83.4	3.71	67.46	MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 8 run
Terry Ligocki	19,134,631	5,443,318	71.6%	46.6	81.69	114.17	chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki	5,443,318	3,400,118	37.5%	16.3	34.87	92.90	chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki	3,400,118	3,303,416	2.8%	14.1	1.90	66.82	MitM_CTL RWL_mod sim 1001 maxT 10000 H 8 mod 3 n 6 run
Terry Ligocki	3,303,416	3,249,427	1.6%	16.5	0.91	55.59	chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 30000 NG_n 7 run
Terry Ligocki	3,249,427	3,155,741	2.9%	13.4	1.94	67.25	MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 6 run
Terry Ligocki	3,155,741	2,246,891	28.8%	14.1	17.93	62.24	chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 30000 NG_n 2 run
Terry Ligocki	2,246,891	2,143,803	4.6%	7.5	3.82	83.19	MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 3 n 1 run
Terry Ligocki	2,143,803	1,938,663	9.6%	7.5	7.58	79.21	MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 1 n 4 run
Terry Ligocki	1,938,663	1,885,153	2.8%	7.5	1.98	71.72	chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
Terry Ligocki	1,885,153	1,848,887	1.9%	10.5	0.96	49.68	MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 1 n 12 run
Terry Ligocki	1,848,887	1,816,027	1.8%	7.6	1.20	67.77	chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 10000 NG_n 5 run
Terry Ligocki	1,816,027	1,688,951	7.0%	10.4	3.40	48.66	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run

References

↑ Shawn Ligocki. 2022. "Extending Up-arrow Notation"

[1] Shawn Ligocki. 2022. "Extending Up-arrow Notation"

[1]

@@ Line 4: / Line 4: @@
 == Top Halters ==
-The highest known scoring machines are:
+The scores are given using [[wikipedia:Knuth's_up-arrow_notation|Knuth's up-arrow notation]] with an extension to decimal tetration<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>. The 20 highest known scoring machines are:
 {| class="wikitable"
 |+
@@ Line 50: / Line 50: @@
 |10 ↑↑ 17.53
 |Shawn Ligocki
+|-
+|{{TM|1RB0RA3RB0LB5LA2LA_2LA4LB1RA3LB5LB1RZ|halt}}
+|10 ↑↑ 17.53
+|Andrew Ducharme
+|-
+|{{TM|1RB3RA4LB5RA5LB4RA_2LA1RZ1RB2LA5LA0LA|halt}}
+|10 ↑↑ 17.08
+|Andrew Ducharme
+|-
+|{{TM|1RB3RA4LA1LA0LA1RZ_2LA0LB1RA1LB5LB2RA|halt}}
+|10 ↑↑ 15.44
+|Andrew Ducharme
+|-
+|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ2LA|halt}}
+|10 ↑↑ 14.35
+|Andrew Ducharme
+|-
+|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ3RA|halt}}
+|10 ↑↑ 14.17
+|Andrew Ducharme
+|-
+|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ1LA|halt}}
+|10 ↑↑ 14.05
+|Andrew Ducharme
+|-
+|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ0RA|halt}}
+|10 ↑↑ 13.69
+|Andrew Ducharme
+|-
+|{{TM|1RB3LA3RA4LB2LB0LA_2LA5LB2RB0RA0RA1RZ|halt}}
+|10 ↑↑ 12.42
+|Andrew Ducharme
+|-
+|{{TM|1RB0LB4LA2RA2RB1LB_2LA4LA3LB5LA1RA1RZ|halt}}
+|10 ↑↑ 11.70
+|Andrew Ducharme
+|-
+|{{TM|1RB2LA1RA1RA5LB1RZ_1LA4RB3RB4LB0RB0RA|halt}}
+|10 ↑↑ 10.39
+|Andrew Ducharme
 |}
 All decimal places are truncated.
-== Filtering ==
+== Phase 1 ==
+The initial phase of enumeration and reduction of holdouts took place in December 2024 and was done by Terry Ligocki using the Ligockis' C++ and Python codes. The initial enumerations generated ~24B(illion) TMs of which ~2,278M were holdout TMs. This was reduced to ~22M holdout TMs (a 99.02% reduction). The details will be given in this table:
+(done to reduce column size:
+<math>*^1</math>= % Reduced,
+<math>*^2</math>= Runtime (hours),
+<math>*^3</math>= Decided,
+<math>*^4</math>= Processed)
+{| class="wikitable sortable" style="text-align: right"
+!rowspan="2" |Done by
+!colspan="2" |Holdout TMs
+!rowspan="2" |<math>*^1</math>
+!rowspan="2" |<math>*^2</math>
+!colspan="2" |TMs/sec/core
+!rowspan="2" |Description
+!rowspan="2" |Data
+|-
+!Input
+!Output
+!<math>*^3</math>
+!<math>*^4</math>
+|-
+|style="text-align:left" |'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|style="text-align:left" |'''---'''
+|}
+== Phase 2 ==
 Starting from Terry Ligocki's [[holdouts list]] of 22,302,296 TMs, additional filtering has been performed:
@@ Line 203: / Line 276: @@
 |style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run
 |}
+==References==
 <!--
 A far more efficient pipeline would immediately apply lr_enum_continue out to 1M steps to Terry Ligocki's holdout list. lr_enum_continue, written in C++, is about 400x faster than Enumerate.py at checking for Lin Recursion. Using Enumerate.py meant its Reverse Engineering decider was applied to all holdouts, and solved 74,089 TMs (0.33% of holdouts)...at the cost of roughly 274.1 hours of compute.