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)>\mathrm{\Sigma }(4,3)>2\uparrow \uparrow \uparrow 2^{2^{32}}$$

The exact status of championship currently remains unclear because of the 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 scores are given using Knuth's up-arrow notation with an extension to decimal tetration. The longest running halters found by Pavel Kropitz are:

Standard format	Approximate sigma scores
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch)	$2\uparrow \uparrow \uparrow 2^{2^{32}}$
1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD (bbch)	$3\uparrow \uparrow \uparrow 88574$

The longest running halters found by comprehensive search are:

Standard format	Approximate sigma score
1RB2LD2LA_1RC0RD2LA_1LA1RZ0LC_2RD2RC0LD (bbch)	10 ↑↑ 53.22643
1RB0LB1RD_2LC1RZ1LB_2LD0LC1RB_2RA2RD1LD (bbch)	10 ↑↑ 42.44165
1RB2RD1LA_2RC1RB1RA_1LC1RZ1LD_2RA2LD0LA (bbch)	10 ↑↑ 33.62777
1RB1LD2LA_1LC1RZ2RD_2LA2RA0LD_2RD0RB0LC (bbch)	10 ↑↑ 33.20324
1RB1RZ0RD_1LC0RC0LD_2LC2LA0RB_2RB1RD2RD (bbch)	10 ↑↑ 33.16838
1RB2LC1LB_2LA2RD0RC_2LB0LA1RB_1RZ2RB2LA (bbch)	10 ↑↑ 32.00113
1RB0RC2RA_1LC2RC0RC_2LC2LD0RB_1RA1RZ0RC (bbch)	10 ↑↑ 27.14142
1RB0LD0RA_1RC1RZ0RB_1LA1RD2RC_2LD2LB0RD (bbch)	10 ↑↑ 21.74030
1RB2RC1RD_2RC0RD1LD_1LA1RZ2RB_2LB2LD1RA (bbch)	10 ↑↑ 21.41425
1RB2LC2LA_1LC0RA1LC_1LA2RD1LB_1RZ2RC0RA (bbch)	10 ↑↑ 20.07678

Potential Champions

In May 2024, Pavel Kropitz found 7 halting TMs that run for a large number of steps. Four of these are equivalent and were analyzed by Racheline in February 2025, while the remaining three were analyzed by Polygon in October 2025.

Pavel listed the halting tapes as:

• 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

These four TMs are equivalent, with 0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch) running longest:

• 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

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 ~633B(illion) TMs of which ~34.4B TMs were holdouts. Also found were ~206B halting TMs and ~392B infinite TMs. The number of holdouts was reduced to ~461M 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 ~45M TMs: ~1.86M halting, ~774K infinite, and ~42.0M holdouts. The second took the ~42.0M holdout TMs and generated a total of ~633B TMs: ~206B halting, ~392B infinite, and ~34.4B 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
Cumulative	632,656,365,801	460,916,384	98.66%	---	---	---	---

Phase 2

When Phase 1 was completed, a set of deciders/parameters were run to reduce the number of holdout TMs. The details are given in the various Stages below.

Stage 1

Starting from the results of Phase 1, Terry Ligocki ran @mxdys' C++ code, "main.exe", using a variety of its deciders with various parameters. A total of 33 variations were run. The holdouts were reduced from ~461B TMs to ~33.9M TMs (a 92.7% reduction). The details are given in the table below, including links to the Google Drive with the holdouts. Entries with multiple lines represent runs where all the commands in the "Description" were applied during one run.

(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	234,834,703	49.05%	96.7	649.48	1,324.10	chr_LRUH 4 chr_H 2 MitM_CTL NG maxT 1000 NG_n 2 run	Google Drive
Terry Ligocki	234,834,703	160,518,206	31.65%	70.9	291.33	920.57	chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 1000 NG_n 2 run
Terry Ligocki	160,518,206	132,296,033	17.58%	41.5	188.86	1,074.17	MitM_CTL RWL_mod sim 1001 maxT 1000 H 4 mod 6 n 1 run
Terry Ligocki	132,296,033	113,193,595	14.44%	54.9	96.57	668.77	MitM_CTL RWL_mod sim 1001 maxT 1000 H 4 mod 1 n 6 run
Terry Ligocki	113,193,595	85,920,795	24.09%	106.8	70.96	294.52	chr_LRUH 16 chr_H 12 MitM_CTL NG maxT 3000 NG_n 2 run
Terry Ligocki	85,920,795	78,674,774	8.43%	28.9	69.62	825.51	MitM_CTL RWL_mod sim 1001 maxT 1000 H 8 mod 2 n 2 run
Terry Ligocki	78,674,774	73,228,547	6.92%	68.7	22.02	318.04	MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 8 H 1 tH 1 n 4 run
Terry Ligocki	73,228,547	67,014,897	8.49%	23.2	74.50	878.02	chr_LRUH 4 chr_H 4 MitM_CTL NG maxT 30000 NG_n 1 run
Terry Ligocki	67,014,897	57,625,231	14.01%	75.6	34.49	246.13	MitM_CTL RWL_mod sim 1001 maxT 3000 H 4 mod 2 n 6 run
Terry Ligocki	57,625,231	48,070,606	16.58%	645.4	4.11	24.80	chr_LRUH 18 chr_H 12 MitM_CTL NG maxT 30000 NG_n 10 run
Terry Ligocki	48,070,606	44,254,286	7.94%	166.3	6.38	80.31	MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 6 H 1 tH 1 n 12 run
Terry Ligocki	44,254,286	40,836,159	7.72%	188.3	5.04	65.29	MitM_CTL RWL_mod sim 1001 maxT 100000 H 3 mod 1 n 2 run
Terry Ligocki	40,836,159	37,460,692	8.27%	192.3	4.88	58.99	chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run chr_LRUH 6 chr_H 6 MitM_CTL NG maxT 3000 NG_n 2 run MitM_CTL RWL_mod sim 1001 maxT 100000 H 2 mod 2 n 1 run MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 6 H 0 tH 1 n 2 run MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 3 n 2 run chr_LRUH 6 chr_H 4 MitM_CTL NG maxT 3000 NG_n 1 run MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 4 H 1 tH 1 n 2 run chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run chr_LRUH 6 chr_H 6 MitM_CTL NG maxT 3000 NG_n 2 run MitM_CTL RWL_mod sim 1001 maxT 1000 H 3 mod 3 n 1 run MitM_CTL RWL_mod sim 1001 maxT 1000 H 8 mod 2 n 1 run MitM_CTL RWL_mod sim 1001 maxT 100000 H 3 mod 2 n 1 run
Terry Ligocki	37,460,692	36,167,570	3.45%	237.7	1.51	43.77	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 3 H 0 tH 1 n 2 run chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 4 run chr_LRUH 6 chr_H 6 MitM_CTL NG maxT 30000 NG_n 2 run chr_LRUH 10 chr_H 8 MitM_CTL NG maxT 10000 NG_n 4 run MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 2 run
Terry Ligocki	36,167,570	34,642,544	4.22%	467.2	0.91	21.50	MitM_CTL RWL_mod sim 1001 maxT 30000 H 3 mod 2 n 24 run
Terry Ligocki	34,642,544	34,339,943	0.87%	383.1	0.22	25.12	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 8 H 1 tH 0 n 24 run
Terry Ligocki	34,339,943	33,860,069	1.40%	666.5	0.20	14.31	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 12 H 2 tH 2 n 8 run
Cumulative	460,916,384	33,860,069	92.70%	---	---	---	---

Stage 2

Starting from the results of Phase 2 Stage, Terry Ligocki ran a variety of enumeration and decider codes. Some of these runs generated new TMs due to the BB(4,3) TNF tree not being fully generated at this time. These reduced the number of holdouts from ~33.9M TMs to ~12.0M TMs (a 64.6% reduction). The details are given in the table below, including links to the Google Drive with the holdouts, halting, and infinite TMs:

(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	33,860,069	21,065,769	37.79%	93.0	38.20	101.11	lr_enum_continue 4x3.in.txt 1000000 4x3.halt.txt 4x3.inf.txt 4x3.holdouts.txt 00 false
Terry Ligocki	21,065,769	18,949,009	10.05%	5,566.1	0.11	1.05	Enumerate.py max-loops 100_000 block-size 2 --tape-limit 1_000 --no-steps --time 1.0 --recursive --exp-linear-rules --lin-steps 0 --no-ctl --no-reverse-engineer --infile 4x3.in.txt --outfile 4x3.out.pb
Terry Ligocki	18,949,009	18,138,027	4,28%	0.4	511.59	11953.46	Reverse_Engineer_Filter.py --infile 4x3.in.txt --outfile 4x3.out.pb
Terry Ligocki	18,138,027	11,985,999	33.92%	4.8	352.73	1,039.95	chr_asth 0 chr_LRUH 1 chr_H 1 MitM_CTL NG maxT 100000 NG_n 3 run
Terry Ligocki	11,985,999	9,988,715	16.66%	640.4	0.87	5.20	chr_LRUH 24 chr_H 16 MitM_CTL NG maxT 30000 NG_n 3 run chr_LRUH 14 chr_H 2 MitM_CTL NG maxT 10000 NG_n 4 run chr_LRUH 2 chr_H 2 MitM_CTL NG maxT 3000 NG_n 5 run chr_asth 0 chr_LRUH 48 chr_H 48 MitM_CTL NG maxT 30000 NG_n 5 run MitM_CTL RWL_mod sim 1001 maxT 10000 H 4 mod 2 n 2 run MitM_CTL RWL_mod sim 1001 maxT 30000 H 6 mod 3 n 2 run MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 1 tH 1 n 4 run chr_LRUH 14 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 0 n 6 run chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 30000 NG_n 2 run chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 30000 NG_n 2 run chr_LRUH 18 chr_H 16 MitM_CTL NG maxT 30000 NG_n 2 run MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 1 tH 0 n 3 run MitM_CTL RWL_mod sim 1001 maxT 100000 H 3 mod 3 n 1 run
Cumulative	33,860,069	9,988,715	70.50%	---	---	---	---