BB(4,3): Difference between revisions

Revision as of 01:24, 27 September 2025

This article is a stub. You can help the BusyBeaverWiki by expanding it.

The Busy Beaver problem for 4 states and 3 symbols is unsolved. The existence of Cryptids in the domain is given by the discovery of Bigfoot in BB(3,3). The current champion appears to be 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) which was discovered by Pavel Kropitz in May 2024 and analyzed by Racheline in Feb 2025, demonstrating the lower bounds:

S(4,3)>\Sigma (4,3)>2\uparrow \uparrow \uparrow 2^{2^{32}}

The exact status of championship currently remains unclear because of this list of "Potential Champions" below which has not yet been fully investigated.

Top Halters

The top 20 longest running halting BB(4,3) TMs are:

Standard format	(approximate) runtime
`0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD` (bbch)	$2\uparrow \uparrow \uparrow 2^{2^{32}}$

Potential Champions

In May 2024, Pavel Kropitz found 7 halting TMs that run for a large number of steps, but have not been analyzed in detail:

https://discord.com/channels/960643023006490684/1026577255754903572/1243253180297646120

Current champion and equivalent TMs:

The current champion 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch): 1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1
0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch): 1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1
1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA (bbch): 1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1
1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB (bbch): 1 2^((80*2^((<(8*2^((8*2^(29) - 2)) - 5); (<(80*2^((b - 10)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4); (<(80*2^((<(80*2^((8*2^((8*2^(29) - 2)) - 3)) - 13)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> - 6)/5) - 17)/9; (40*2^((8*2^((a - 11)/5) - 2)) - 4); (40*2^(2) - 4)> + 4)> - 10)/5) - 3)) 1 0 1 2 1^2 Z> 1 2^2 1

Others:

1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_2RB2RA2RD (bbch): 1 Z> 1^((8*<7; (6*2^((4b + 14)) - 4); (6*2^((48*2^(21) - 2)) - 4)> + 33)) 2
1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch): 1 Z> 1^((2*<(<(<(16*2^(92) - 3); (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<(24*2^((24*2^(<(24*2^((24*2^(92) - 3)) - 2); (24*2^(b) - 4); 92>) - 3)) - 1); (24*2^(b) - 4); 2>) - 3)) - 11)> + 8)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 5)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 19))
1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD (bbch): 1 Z> 1^(162*3^((3*<(243*3^(6) - 5)/2; (<(54*3^((3b + 11)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1); (<(54*3^((3*<(54*3^(7) - 3); (54*3^((3b + 14)/2) - 6); (54*3^((81*3^(7) - 2)) - 6)> + 14)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1)> + 11)/2)) 2

Phase 1

The initial phase of enumeration and reduction of holdouts took place in December 2024 and was done by Terry Ligocki using the Ligocki's C++ and Python codes. The initial enumerations generated ~663B(illion) TMs of which ~34B holdout TMs. This was reduced to ~461M holdout TMs (a 98.66% reduction). The details are 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	Source	Data
Done by	Input	Output	$*^{1}$	$*^{2}$	$*^{3}$	$*^{4}$	Description	Source	Data
---	---	---	---	---	---	---	---	---

Phase 2

In this phase, Terry Ligocki used mxdys' C++ code to find and apply deciders/parameters to the holdout from phase 1. This took place in September 2025. The initial ~461M holdout TMs was reduced to ~98M (a 78.8% reduction). The details are given in this table:

(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	Source	Data
Done by	Input	Output	$*^{1}$	$*^{2}$	$*^{3}$	$*^{4}$	Description	Source	Data
---	---	---	---	---	---	---	---	---

@@ Line 32: / Line 32: @@
 * {{TM|1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD|halt}}: 1 Z> 1^((2*<(<(<(16*2^(92) - 3); (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<(24*2^((24*2^(<(24*2^((24*2^(92) - 3)) - 2); (24*2^(b) - 4); 92>) - 3)) - 1); (24*2^(b) - 4); 2>) - 3)) - 11)> + 8)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 5)/3; (24*2^((24*2^(<(b + 10); (24*2^(b) - 4); 2>) - 3)) - 11); (24*2^((24*2^(<1; (24*2^(b) - 4); 2>) - 3)) - 11)> + 19))
 * {{TM|1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD|halt}}: 1 Z> 1^(162*3^((3*<(243*3^(6) - 5)/2; (<(54*3^((3b + 11)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1); (<(54*3^((3*<(54*3^(7) - 3); (54*3^((3b + 14)/2) - 6); (54*3^((81*3^(7) - 2)) - 6)> + 14)/2) - 2); (54*3^((3b + 14)/2) - 6); (54*3^(7) - 6)> + 1)> + 11)/2)) 2
+== Phase 1 ==
+The initial phase of enumeration and reduction of holdouts took place in December 2024 and was done by Terry Ligocki using the Ligocki's C++ and Python codes. The initial enumerations generated ~663B(illion) TMs of which ~34B holdout TMs. This was reduced to ~461M holdout TMs (a 98.66% reduction). The details are 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" |Source
+!rowspan="2" |Data
+|-
+!Input
+!Output
+!<math>*^3</math>
+!<math>*^4</math>
+|-
+|style="text-align:left" |'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|style="text-align:left" |'''---'''
+|style="text-align:left" |'''---'''
+|}
+== Phase 2 ==
+In this phase, Terry Ligocki used mxdys' C++ code to find and apply deciders/parameters to the holdout from phase 1. This took place in September 2025. The initial ~461M holdout TMs was reduced to ~98M (a 78.8% reduction). The details are given in this table:
+(done to reduce column size:
+<math>*^1</math>= % Reduced,
+<math>*^2</math>= Compute Time (core-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" |Source
+!rowspan="2" |Data
+|-
+!Input
+!Output
+!<math>*^3</math>
+!<math>*^4</math>
+|-
+|style="text-align:left" |'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|'''---'''
+|style="text-align:left" |'''---'''
+|style="text-align:left" |'''---'''
+|}
 [[Category:BB Domains]]