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

XnoobSpeakable and Lúkos are working on applying mxdys' deciders/parameters to the remaining holdouts. The previous holdouts list by Terry Ligocki was split up into 8696 files containing 50,000 holdouts each* (*the last one actually has 37,751) and the deciders were applied to the files individually. For the second round, there were 1296 files of this type.

The details will be given in this table:

Done by	Holdout TMs		% Reduced	Description	Data
	Input	Output
XnoobSpeakable, Lúkos	434,787,751	64,777,377	85.1%	Phase 2 run 1	Google Drive
XnoobSpeakable, Lúkos	64,777,377	Predicted 36.9M	---	Phase 2 run 2, run in progress	---

Phase 2 Data

Here we will list the deciders applied during the various runs of Phase 2. Each line shows a decider and how many TMs that decider ran. Each decider within a run was not applied in a specific order.

Phase 2 run 1:

chr_LRUH 4 chr_H 4 MitM_CTL NG maxT 1000 NG_n 2 run 86569103
chr_LRUH 4 chr_H 4 MitM_CTL NG maxT 1000 NG_n 1 run 26093656
chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 3000 NG_n 2 run 13972946
MitM_CTL RWL_mod sim 1001 maxT 1000 H 6 mod 3 n 2 run 7190617
chr_LRUH 10 chr_H 6 MitM_CTL NG maxT 1000 NG_n 2 run 90302784
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 16 H 1 tH 1 n 4 run 4342619
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 12 H 0 tH 1 n 2 run 11764327
chr_LRUH 2 chr_H 2 MitM_CTL NG maxT 1000 NG_n 1 run 55465842
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 2 n 1 run 17805678
MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 2 H 0 tH 0 n 1 run 12623067
chr_LRUH 2 chr_H 0 MitM_CTL NG maxT 3000 NG_n 2 run 2240499
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 4 H 1 tH 1 n 2 run 10223131
chr_LRUH 6 chr_H 4 MitM_CTL NG maxT 10000 NG_n 1 run 2901053
chr_LRUH 22 chr_H 12 MitM_CTL NG maxT 3000 NG_n 2 run 28515052

Phase 2 run 2 (No solved TM count as this run has not been completed):

MitM_CTL RWL_mod sim 1001 maxT 3000 H 8 mod 2 n 2 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 3 n 20 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 8 mod 3 n 2 run
MitM_CTL RWL_mod sim 1001 maxT 10000 H 2 mod 2 n 1 run
chr_LRUH 10 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 3 H 1 tH 0 n 6 run
MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 6 H 1 tH 1 n 2 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 6 mod 3 n 1 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 16 H 1 tH 1 n 1 run
MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 0 tH 1 n 2 run
chr_LRUH 18 chr_H 12 MitM_CTL NG maxT 10000 NG_n 4 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 3 n 1 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 8 H 0 tH 0 n 4 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 4 mod 4 n 6 run
chr_LRUH 18 chr_H 12 MitM_CTL NG maxT 3000 NG_n 2 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 3 mod 4 n 8 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 6 H 0 tH 1 n 3 run
chr_LRUH 6 chr_H 6 MitM_CTL NG maxT 3000 NG_n 2 run