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 is 1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch) which was discovered by Pavel Kropitz in May 2024 along with 6 other long running machines. It was analyzed by Polygon in Oct 2025, demonstrating the lower bounds:

$$S(4,3)>\mathrm{\Sigma }(4,3)>10{\uparrow }^{4}4$$

Top Halters

The longest running halting BB(4,3) TMs are split amongst two classes: the pentational and hexational TMs found by Pavel Kropitz outlined in the Potential Champions section, and the tetrational TMs found by comprehensive holdout filtering by Terry Ligocki. 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
1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch)	$10{\uparrow }^{4}4$
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch)	$2\uparrow \uparrow \uparrow 2^{2^{32}}$
1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD (bbch)	$3\uparrow \uparrow \uparrow 88574$

The top 20 scoring halting machines found by comprehensive search are:

Standard format	Approximate sigma score
1RB0LC1RC_1LA2RB1LB_1RC2LA0RD_2LB1RZ2LC (bbch)	~10 ↑↑ 190.21359
1RB2LA1RA_1LA0RC1LC_1LC2RB0LD_2RA1RZ2RC (bbch)	~10 ↑↑ 190.21359
1RB2LC1RA_1LA0RD2RB_2LD0RC2LD_2LA1RZ0RD (bbch)	~10 ↑↑ 166.03664
1RB2LC1RA_1LA0RD2RB_2LD2LA2LD_2LA1RZ0RD (bbch)	~10 ↑↑ 166.03664
1RB2LC1RA_1LA2LD2RB_2LD0RC2LD_2LA1RZ0RD (bbch)	~10 ↑↑ 166.03664
1RB2LC1RA_1LA2LD2RB_2LD2LA1LB_2LA1RZ0RD (bbch)	~10 ↑↑ 166.03664
1RB2LC1RA_1LA2LD2RB_2LD2LA2LD_2LA1RZ0RD (bbch)	~10 ↑↑ 166.03664
1RB1RC2RB_2LC2LB0LC_1RA1LD0RB_2RA0LC1RZ (bbch)	~10 ↑↑ 128.27662
1RB2LC1RA_1LA2RA2RB_1LD2LA0RC_1RA1RZ0RB (bbch)	~10 ↑↑ 127.14811
1RB1RC2LA_2LC0LA1LD_0LD0LB1RZ_2RA2RD1LB (bbch)	~10 ↑↑ 107.56135
1RB2LB1LA_0LC2RA0RA_2LA2LD1RZ_2LB2LC2LC (bbch)	~10 ↑↑ 86.27662
1RB1LD1RC_0LC0RB0LD_2RA1LA1RZ_2LC2LB0LA (bbch)	~10 ↑↑ 86.15130
1RB0LD0RC_1RC1RZ0RB_1LA2RD2RC_2LD2LB0RD (bbch)	~10 ↑↑ 85.27623
1RB2RB1LC_2LB2RA0RB_0LC1RZ2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_0RC1RZ2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_1LC1RZ2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_1RC1RZ2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_1RZ---2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_1RZ2LD2LD_2LA1RA0LB (bbch)	~10 ↑↑ 83.00625
1RB2RB1LC_2LB2RA0RB_2LC1RZ2LD_2LA2RA0LB (bbch)	~10 ↑↑ 83.00625

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.

Standard format	Approximate sigma scores
1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_0RB2RA2RD (bbch)	$10{\uparrow }^{4}4$
0RB1RZ0RB_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch)*	$2\uparrow \uparrow \uparrow 2^{2^{32}}$
1RB2LB0LB_2LC2LA0LA_2RD1LC1RZ_1RA2LD1RD (bbch)	$3\uparrow \uparrow \uparrow 88574$
1RB1RD1LC_2LB1RB1LC_1RZ1LA1LD_2RB2RA2RD (bbch)	$10\uparrow \uparrow 9.873987$

*equivalent to 0RB1RZ1RC_1RC1LB2LB_1LB2RD1LC_1RA2RC0LD (bbch), 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ0RA (bbch) and 1RB1LA2LA_1LA2RC1LB_1RD2RB0LC_0RA1RZ1RB (bbch).

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 ~9.4M TMs (a 72.2% 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	Google Drive
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
Terry Ligocki	9,988,715	9,401,447	5.88%	1,398.7	0.12	1.98	chr_asth 0 chr_LRUH 60 chr_H 60 MitM_CTL NG maxT 100000 NG_n 5 run chr_LRUH 22 chr_H 12 MitM_CTL NG maxT 100000 NG_n 6 run chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 100000 NG_n 2 run MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 16 H 1 tH 0 n 10 run chr_LRUH 4 chr_H 0 MitM_CTL NG maxT 1000000 NG_n 2 run MitM_CTL RWL_mod sim 1001 maxT 30000 H 4 mod 6 n 1 run MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 3 n 3 run MitM_CTL RWL_mod sim 1001 maxT 30000 H 4 mod 2 n 2 run MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 8 H 2 tH 2 n 2 run MitM_CTL RWL_mod sim 1001 maxT 30000 H 3 mod 2 n 3 run MitM_CTL RWL_mod sim 1001 maxT 10000 H 4 mod 6 n 2 run MitM_CTL RWL_mod sim 1001 maxT 30000 H 4 mod 2 n 1 run MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 4 H 1 tH 1 n 2 run MitM_CTL RWL_mod sim 1001 maxT 10000 H 4 mod 5 n 2 run
Cumulative	33,860,069	9,401,447	72.23%	---	---	---	---