BB(3,4)

The Busy Beaver problem for 3 states and 4 symbols is unsolved, with the existence of Cryptids in the domain being given by the discovery of Bigfoot in BB(3,3). The current BB(3,4) champion is 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch). It runs for $2\uparrow ^{15}5$ steps before halting. It was discovered by Pavel Kropitz in 2024 and was analysed by Shawn Ligocki in the same year.

Top Halters

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

Standard format	(approximate) runtime
1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC (bbch)	$2\uparrow ^{15}5$
1RB1RZ1LA2RB_1RC3RC1LA2LB_2LB2RC1LC3RB (bbch)	$2\uparrow ^{12}4$
1RB0LB1RZ3LA_0LC3RB3RC1LB_2RB2LA3RA1LC (bbch)	$10\uparrow \uparrow {2\,048}$

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 600,253,156,787 TMs of which 42,391,877,333 were holdout TMs. Also found were 202,014,400,019 halting TMs and 355,846,879,435 infinite TMs. The number of holdouts were reduced to 434,787,751 TMs (a 98.97% reduction).

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

lr_enum 3 4 8 /dev/null /dev/null 3x4.unk.txt false
00 <= XX < 47: lr_enum_continue 3x4.in.XX 1000 /dev/null /dev/null 3x4.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(3,4) of depth 8 and outputs the holdouts to 3x4.unk.txt. This file was then divided into 48 pieces, 3x4.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: 3x4.unk.txt.XX.

For these runs the first command generated a total of 22,366,747 TMs: 932,198 halting, 235,446 infinite, and 21,199,103 holdouts. The second took the 22,366,747 holdout TMs and generated a total of 600,253,156,787 TMs: 202,014,400,019 halting, 355,846,879,435 infinite, and 42,391,877,333 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	42,391,877,333	32,247,381,725	23.93%	788.0	3,576.08	14,943.74	Reverse_Engineer_Filter.py	Google Drive
Terry Ligocki	32,247,381,725	12,789,441,316	60.34%	6,185.2	873.85	1,448.22	CPS_Filter.py --block-size=1
Terry Ligocki	12,789,441,316	4,332,283,583	66.13%	4,771.0	492.39	744.62	CPS_Filter.py --block-size=2
Terry Ligocki	4,332,283,583	2,796,143,404	35.46%	7,873.1	54.20	152.85	CPS_Filter.py --block-size=3
Terry Ligocki	2,796,143,404	1,398,734,288	49.98%	10,239.4	37.91	75.85	Enumerate.py --max-loops=1_000 --block-size=2 --time=10 --lin-steps=0 --no-reverse-engineer --save-freq=10_000
Terry Ligocki	1,398,734,288	764,851,053	45.32%	3,203.1	54.97	121.30	Enumerate.py --max-loops=10_000 --block-size=12 --no-steps --time=0.01 --lin-steps=0 --no-ctl --no-reverse-engineer --save-freq=10_000
Terry Ligocki	764,851,053	581,654,405	23.95%	1,925.3	26.43	110.35	CPS_Filter.py --min-block-size=4 --max-block-size=12 --max-steps=1_000
Terry Ligocki	581,654,405	434,787,751	25.25%	9,042.5	4.51	17.87	CPS_Filter.py --min-block-size=4 --max-block-size=6 --max-steps=10_000

Phase 2

Xnoob545 and Lúkos from the bbchallenge discord are working on applying mxdys' deciders/parameters to the remaining holdouts. 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
	Input	Output			$*^{3}$	$*^{4}$
---	---	---	---	---	---	---	---