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 known 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 2048$
1RB1RZ1LA2RB_2RC3RC3LB2RA_2LB3RB3LC1LA (bbch)	$10\uparrow \uparrow 189$
1RB3LA1RA2LB_2LC1RA2RC3RB_1RZ1LA2RA3RA (bbch)	$10\uparrow \uparrow 188$
1RB1LB2LA3LC_1LA2RB3RA1LB_1RZ1RB2LB3LB (bbch)	$10\uparrow \uparrow 188$
1RB1RA3LA3RB_2LC2RC1LB2RA_2RA2RB0LB1RZ (bbch)	$10\uparrow \uparrow 150$
1RB2LB1RZ3LA_1LA3RC2LC1LC_2LA3RC0RA1LB (bbch)	$10\uparrow \uparrow 130$
1RB2LB1RZ3LA_1LA3RC3LB1LC_2RA3RC0RA1LB (bbch)	$10\uparrow \uparrow 130$
1RB2LC1RC2RA_1LA3RA2RB1RZ_3LB2LC1RA0LB (bbch)	$10\uparrow \uparrow 130$
1RB1RA1LB3RA_1RC3LB1LC1RC_2LA2RA1RZ0LA (bbch)	$10\uparrow \uparrow 96$
1RB1RA1LB3RA_1RC3LB1LC1RC_2LA2RA1RZ1RB (bbch)	$10\uparrow \uparrow 96$
1RB3LC0RA1RC_2LA1RZ3LA2RB_3LA0RA1LA0RA (bbch)	$10\uparrow \uparrow 95$
1RB3LC0RA1RC_2LA1RZ3LA2RB_3LA0RA3LB0RA (bbch)	$10\uparrow \uparrow 95$
1RB2LA1RA1RC_1LA3LC3RB1RC_3LA1RZ3LB2RC (bbch)	$10\uparrow \uparrow 84$
1RB0LB1RA2LB_2RC3LB3RB2LA_2LC1RZ1LA2RB (bbch)	$10\uparrow \uparrow 76$
1RB1LA1RZ0LB_2LC2LB1RC1RB_3LA3LC0LC0RA (bbch)	$10\uparrow \uparrow 76$
1RB2RA1LA1LB_2RC3RB1RZ3LC_2LA1RC1RB0RA (bbch)	$10\uparrow \uparrow 70$
1RB3LA1RZ3LC_2LA3LB3RC1RB_3RB1LC1RA0LB (bbch)	$10\uparrow \uparrow 69$
1RB3LA1LC1RA_0LC1RZ1RB2RB_3LA2LC1RC3RC (bbch)	$10\uparrow \uparrow 69$

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 was 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. These files can be called subtasks. Lúkos made a Python script to compute the subtasks in parallel, based off of XnoobSpeakable's earlier imperfect script.

Certain data such as TMs/sec/core is unavailable, because the amount of time the computation took was not kept track of.

Stage 3 is a lr_enum_continue computation to 1 million steps. While Lúkos did not contribute to computing stage 3, he did create a Python script to compute it in bulk, which XnoobSpeakable used.

For the "Contribution" column, the first number is the amount of subtasks solved by XnoobSpeakable, the 2nd is the amount solved by Lúkos. Note that the counts are unequal, because Lúkos has a slower CPU with a lower core count. According to XnoobSpeakable, the time contribution from both contributors is roughly equal. Lúkos also worked on the Python scripts used, while XnoobSpeakable worked on compiling holdouts lists and finding optimal deciders to apply.

Peacemaker II worked on verifying the validity of the results as well as providing solved TM counts per decider. Stages 1, 2, and 4 have been validated - no dropped TMs. XnoobSpeakable verified stage 6.

The details will be given in this table:

Done by	Holdout TMs		% Reduced	Description	Subtasks	Contribution	Data
	Input	Output
XnoobSpeakable, Lúkos	434,787,751	64,777,377	85.1%	Phase 2 stage 1	8696	7696 / 1000	Google Drive
XnoobSpeakable, Lúkos	64,777,377	37,016,957	42.9%	Phase 2 stage 2	1296	1000 / 296	Google Drive
XnoobSpeakable	37,016,957	26,266,261	29.0%	Phase 2 stage 3	741	741 / 0	Google Drive
XnoobSpeakable, Lúkos	26,266,261	22,396,711	14.7%	Phase 2 stage 4	526	485 / 41	Google Drive
XnoobSpeakable, Lúkos	22,396,711	17,983,810	19.7%	Phase 2 stage 5	448	390 / 58	Google Drive
XnoobSpeakable, Lúkos	17,983,810	15,564,491	13.5%	Phase 2 stage 6	360	300 / 60	Google Drive

Phase 2 Data

Here we will list the deciders applied during the various stages of Phase 2. Each line shows a decider and how many TMs that decider solved (last number; provided by Peacemaker II). Each decider within a stage was not applied in a specific order.

Phase 2 stage 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 stage 2:

MitM_CTL RWL_mod sim 1001 maxT 1000 H 3 mod 4 n 8 run 1030303
MitM_CTL RWL_mod sim 1001 maxT 3000 H 8 mod 2 n 2 run 1465523
chr_LRUH 18 chr_H 12 MitM_CTL NG maxT 10000 NG_n 4 run 5232902
chr_LRUH 18 chr_H 12 MitM_CTL NG maxT 3000 NG_n 2 run 1720994
MitM_CTL RWL_mod sim 1001 maxT 3000 H 8 mod 3 n 2 run 555883
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 3 H 1 tH 0 n 6 run 290547
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 3 n 1 run 67506
chr_LRUH 10 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run 1577979
chr_LRUH 6 chr_H 6 MitM_CTL NG maxT 3000 NG_n 2 run 1604533
MitM_CTL RWL_mod sim 1001 maxT 3000 H 4 mod 4 n 6 run 10012948
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 8 H 0 tH 0 n 4 run 526822
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 16 H 1 tH 1 n 1 run 34821
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 6 H 0 tH 1 n 3 run 356375
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 3 n 20 run 1970422
MitM_CTL RWL_mod sim 1001 maxT 1000 H 6 mod 3 n 1 run 443339
MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 0 tH 1 n 2 run 518824
MitM_CTL RWL_mod sim 1001 maxT 10000 H 2 mod 2 n 1 run 61865
MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 6 H 1 tH 1 n 2 run 288834

Phase 2 stage 3 was not computed with mxdys' main.exe, but rather with lr_enum_continue from busy-beaver for 1 million steps; the command is provided below:

lr_enum_continue ./in.txt 100000 ./halt.txt ./inf.txt ./unknown.txt "" false
</syntaxhighlight>Phase 2 stage 4:<syntaxhighlight>
chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 3000 NG_n 2 run 202520
chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 3000 NG_n 1 run 559013
MitM_CTL RWL_mod sim 1001 maxT 3000 H 1 mod 4 n 1 run 1584
chr_asth 0 chr_LRUH 1 chr_H 1 MitM_CTL NG maxT 10000 NG_n 1 run 148544
chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 100000 NG_n 1 run 812666
chr_asth 0 chr_LRUH 48 chr_H 48 MitM_CTL NG maxT 10000 NG_n 3 run 2043171
MitM_CTL RWL_mod sim 1001 maxT 1000 H 4 mod 2 n 1 run 102052

Phase 2 stage 5 (no TM count per decider is available at this time):

MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 6 H 0 tH 1 n 10 run
MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 16 H 1 tH 1 n 1 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 3 mod 6 n 2 run
chr_LRUH 2 chr_H 0 MitM_CTL NG maxT 10000 NG_n 3 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 4 mod 5 n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 3 H 1 tH 0 n 2 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 3 mod 1 n 1 run
MitM_CTL RWL_mod sim 1001 maxT 1000 H 2 mod 3 n 2 run
chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 100000 NG_n 5 run
MitM_CTL RWL_mod sim 1001 maxT 10000 H 4 mod 4 n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 6 H 0 tH 1 n 3 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 16 H 1 tH 0 n 1 run
MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 3 n 1 run
chr_LRUH 4 chr_H 2 MitM_CTL NG maxT 30000 NG_n 3 run
chr_LRUH 16 chr_H 12 MitM_CTL NG maxT 30000 NG_n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 8 H 2 tH 1 n 2 run
chr_asth 0 chr_LRUH 12 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 16 H 1 tH 0 n 6 run
MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 16 H 0 tH 0 n 1 run
chr_LRUH 6 chr_H 2 MitM_CTL NG maxT 10000 NG_n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 1000 LRUH 3 H 1 tH 0 n 2 run
chr_LRUH 2 chr_H 0 MitM_CTL NG maxT 3000 NG_n 1 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 2 mod 3 n 1 run
chr_LRUH 3 chr_H 1 MitM_CTL NG maxT 100000 NG_n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 6 H 1 tH 0 n 4 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 2 mod 2 n 2 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 4 mod 4 n 1 run
MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 4 H 2 tH 0 n 1 run
chr_LRUH 4 chr_H 0 MitM_CTL NG maxT 1000 NG_n 2 run
MitM_CTL RWL_mod sim 1001 maxT 30000 H 2 mod 1 n 1 run
MitM_CTL RWL_mod sim 1001 maxT 3000 H 3 mod 6 n 1 run
chr_asth 0 chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 10000 NG_n 2 run
chr_asth 0 chr_LRUH 60 chr_H 60 MitM_CTL NG maxT 30000 NG_n 2 run
MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 0 tH 0 n 1 run
MitM_CTL RWL_mod sim 1001 maxT 30000 H 3 mod 2 n 1 run
chr_LRUH 4 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
MitM_CTL RWL_mod sim 1001 maxT 1000 H 3 mod 3 n 1 run
chr_asth 0 chr_LRUH 4 chr_H 4 MitM_CTL NG maxT 3000 NG_n 2 run

Phase 2 stage 6:

python "+str(pl.Path("../../Code/Enumerate.py"))+" --infile="+str(pl.Path("./in.txt"))+" --outfile="+str(pl.Path("./out.pb"))+" --max-loops=990_000 --tape-limit=9_900 --no-steps --time="+str(time)+" --recursive --exp-linear-rules  --lin-steps=0 --no-ctl --save-freq=10_000

XnoobSpeakable ran Enumerate.py with a 0.15s/TM time limit, Lúkos ran it with a 0.75s/TM time limit.