BB(4,3)

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 longest running halting BB(4,3) TMs are split amongst two classes: the pentational TMs found by Pavel Kropitz outlined in the Potential Champions section, and the tetrational TMs found by comprehensive holdout filtering by Andrew Ducharme. The current champion is:

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

The longest running halters found by comprehensive search are:

Standard format	Approximate sigma score
1RB2LD2LA_1RC0RD2LA_1LA1RZ0LC_2RD2RC0LD	~10↑↑53.22643
1RB0LB1RD_2LC1RZ1LB_2LD0LC1RB_2RA2RD1LD	~10↑↑42.44165
1RB0LD0RA_1RC1RZ0RB_1LA1RD2RC_2LD2LB0RD	~10↑↑21.74030
1RB1RD2LD_1LC1RZ0LB_2RA0LB2LC_2RD2RB0LD	~10↑↑20.03189
1RB2LD2RA_1LC2RC0RB_2LC2LD0RC_1RA1RZ0RB	~10↑↑19.02738
1RB2LB2RA_1LC2RC0RB_2LC2LD0RC_1RA1RZ0RB	~10↑↑19.02738
1RB0LB1RD_2LA1LC1LB_2RD1RZ2LC_2RA2RD1LD	~10↑↑18.02190
1RB0RA1RA_2LC1RZ2RB_2LA2LC0RD_1LC1RD1LD	~10↑↑16.37817
1RB1RZ1RA_1LC2LA2RB_0LD2LC1RC_2RA0RD0LA	~10↑↑13.74370

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 Ligockis' C++ and Python codes. The initial enumerations generated 632,696,275,325 TMs of which 34,413,860,527 were holdout TMs. Also found were 206,487,114,662 halting TMs and 391,755,390,612 infinite TMs. The number of holdouts were reduced to 460,916,384 holdout TMs (a 98.66% reduction).

Two C++ programs were run before the filters in the table.

lr_enum 4 3 8 /dev/null /dev/null 4x3.unk.txt false
00 <= XX < 47: lr_enum_continue 4x3.in.XX 1000 /dev/null /dev/null 4x3.unk.txt.XX XX false

Both do the initial enumeration and simple filtering. The "/dev/null" in both commands would be files where the halting and infinite TMs would be stored. The first command generates the TMs from a TNF tree for BB(4,3) of depth 8 and outputs the holdouts to 4x3.unk.txt. This file was then divided into 48 pieces, 4x3.in.XX, 0 <= XX < 47. The second commands (one for each XX) continues the enumeration by running each TM for 1,000 steps. It classifies each as halting, infinite, or unknown/holdout. Again, the halting and infinite TMs are "written" to /dev/null, i.e., they aren't saved. The holdouts are stored in 48 files: 4x3.unk.txt.XX.

For these runs the first command generated a total of 44,665,207 TMs: 1,861,171 halting, 774,153 infinite, and 42,029,883 holdouts. The second took the 42,029,833 holdout TMs and generated a total of 632,656,365,801 TMs: 206,487,114,662 halting, 391,755,390,612 infinite, and 34,413,860,527 holdouts. These holdouts were used as a starting point of the filters below.

The "Description" column in the table below contain the command run. Two options are not given, "--infile=..." and an "--outfile=...". These are necessary and specify where to read and write the results, respectively. Note: The work flow was to divide the input holdouts into 48 pieces, run the command on each piece simultaneously on one of 48 cores, and then combine the 48 results into a group of holdouts.

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	Data
	Input	Output			$*^{3}$	$*^{4}$
Terry Ligocki	34,413,860,527	30,874,934,791	10.28	646.6	1,520.36	14,784.57	Reverse_Engineer_Filter.py	Google Drive
Terry Ligocki	30,874,934,791	12,942,386,396	58.08	4,134.8	1,204.72	2,074.19	CPS_Filter.py --block-size=1
Terry Ligocki	12,942,386,396	4,534,322,415	64.97	3,361.1	694.88	1,069.62	CPS_Filter.py --block-size=2
Terry Ligocki	4,534,322,415	2,959,598,830	34.73	3,318.1	131.83	379.59	CPS_Filter.py --block-size=3
Terry Ligocki	2,959,598,830	1,651,940,618	44.18	2,700.6	134.50	304.42	Enumerate.py --max-loops=1_000 --block-size=2 --no-steps --time=0.002 --lin-steps=0 --no-reverse-engineer --save-freq=10_000
Terry Ligocki	1,651,940,618	854,984,279	48.24	2,276.3	97.25	201.59	Enumerate.py --max-loops=10_000 --block-size=12 --no-steps --time=0.005 --lin-steps=0 --no-ctl --no-reverse-engineer --save-freq=10_000
Terry Ligocki	854,984,279	683,163,325	20.10	430.1	110.96	552.15	CPS_Filter.py --block-size=4 --max-steps=1_000
Terry Ligocki	683,163,325	460,916,384	32.53	5,507.9	11.21	34.45	CPS_Filter.py --min-block-size=1 --max-block-size=6 --max-steps=10_000

Phase 2

In this phase, Terry Ligocki used mxdys' C++ code, main.cpp, to find and apply deciders/parameters to the holdouts from Phase 1. This took place in September 2025. The initial ~461M holdout TMs were reduced to ~98M (a 78.8% reduction). The details are given in this table, including links to the Google Drive with the holdouts and details of the computation:

(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
	Input	Output			$*^{3}$	$*^{4}$
Terry Ligocki	460,916,384	114,288,393	75.20%	30.3	3,181.42	4,230.39	chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 1000 NG_n 8 run	Google Drive
Terry Ligocki	114,288,393	105,922,759	7.32%	7.4	315.37	4,308.43	MitM_CTL RWL_mod sim 1001 maxT 1000 H 8 mod 5 n 3 run
Terry Ligocki	105,922,759	98,061,985	7.42%	7.4	296.09	3,989.74	MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 4 H 0 tH 2 n 2 run
Terry Ligocki	98,061,985	97,770,372	0.30%	1.5	54.14	18,206.56	chr_asth 0 chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 1000 NG_n 6 run
Terry Ligocki	97,770,372	97,705,106	0.07%	1.7	10.45	15,652.68	MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 12 H 2 tH 0 n 6 run
Terry Ligocki	97,705,106	97,701,052	0.00%	1.0	1.09	26,353.22	MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 4 H 2 tH 0 n 5 run