BB(2,6)

The 2-state, 6-symbol Busy Beaver problem, BB(2,6), is unsolved. With cryptids like Hydra in the preceding domain BB(2,5), we know that we must solve a Collatz-like problem in order to solve BB(2,6).

The current BB(2,6) champion 1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch) was discovered by Pavel Kropitz in May 2023, proving the lower bound:$$S(2,6)>\mathrm{\Sigma }(2,6)>10\uparrow \uparrow 10\uparrow \uparrow 10^{10^{115}}>10\uparrow \uparrow \uparrow 3$$

Top Halters

The scores are given using Knuth's up-arrow notation with an extension to decimal tetration. The 20 highest known scoring machines are:

TM	Approximate sigma score	Discoverer
1RB3RB5RA1LB5LA2LB_2LA2RA4RB1RZ3LB2LA (bbch)	10 ↑↑↑ 3	Pavel Kropitz
1RB2LA1RZ1RB5RB0RB_2LA4RA3LB5LB5RA4LB (bbch)	10 ↑↑ 19892.08	Peacemaker II
1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ (bbch)	10 ↑↑ 91.17	Pavel Kropitz
1RB2LA1RA4LA5RA0LB_1LA3RA2RB1RZ3RB4LA (bbch)	10 ↑↑ 70.27	Shawn Ligocki
1RB2LB1RZ3LA2LA4RB_1LA3RB4RB1LB5LB0RA (bbch)	10 ↑↑ 69.68	Shawn Ligocki
1RB2LB0RA2RA5RA1LB_2LA4RB3LB2RB0RB1RZ (bbch)	10 ↑↑ 54.90	Andrew Ducharme
1RB3RB1LB5LA2LB1RZ_2LA3RA4RB2LB0LA4RB (bbch)	10 ↑↑ 42.17	Andrew Ducharme
1RB3LB0RB5RA1LB1RZ_2LB3LA4RA0RB0RA2LB (bbch)	10 ↑↑ 40.07	Andrew Ducharme
1RB3LB3RB4LA2LA4LA_2LA2RB1LB0RA5RA1RZ (bbch)	10 ↑↑ 21.54	Shawn Ligocki
1RB2LB3LA1RA0RA1RZ_1LA2RB1LB4RB5RA3LA (bbch)	10 ↑↑ 20.58	Shawn Ligocki
1RB0RA3RB0LB1RA2LA_2LA4LB1RA3LB5LB1RZ (bbch)	10 ↑↑ 17.53	Shawn Ligocki
1RB0RA3RB0LB5LA2LA_2LA4LB1RA3LB5LB1RZ (bbch)	10 ↑↑ 17.53	Andrew Ducharme
1RB3RA4LB5RA5LB4RA_2LA1RZ1RB2LA5LA0LA (bbch)	10 ↑↑ 17.08	Andrew Ducharme
1RB3RA4LA1LA0LA1RZ_2LA0LB1RA1LB5LB2RA (bbch)	10 ↑↑ 15.44	Andrew Ducharme
1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ2LA (bbch)	10 ↑↑ 14.35	Andrew Ducharme
1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ3RA (bbch)	10 ↑↑ 14.17	Andrew Ducharme
1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ1LA (bbch)	10 ↑↑ 14.05	Andrew Ducharme
1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ0RA (bbch)	10 ↑↑ 13.69	Andrew Ducharme
1RB3LA3RA4LB2LB0LA_2LA5LB2RB0RA0RA1RZ (bbch)	10 ↑↑ 12.42	Andrew Ducharme
1RB0LB4LA2RA2RB1LB_2LA4LA3LB5LA1RA1RZ (bbch)	10 ↑↑ 11.70	Andrew Ducharme

All decimal places are truncated.

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 ~24B(illion) TMs of which ~2,278B were holdout TMs. This was reduced to ~22M holdout TMs (a 99.02% reduction). The details are given in this table, including links to the Google Drive with the holdouts and details of the computation:

(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
	Terry Ligocki	2,278,655,696			2,109,114,609	7.44%			40.9	1,150.90	15,468.23	Reverse_Engineer_Filter.py	Google Drive
Terry Ligocki	2,109,114,609	683,067,538	67.61%	452.8	874.77	1,293.79	CPS_Filter.py --block-size=1
Terry Ligocki	683,067,538	210,993,434	69.11%	396.4	330.85	478.72	CPS_Filter.py --block-size=2
Terry Ligocki	210,993,434	141,680,232	32.85%	273.9	70.29	213.97	CPS_Filter.py --block-size=3 --max_steps=10_000
Terry Ligocki	141,680,232	66,029,536	53.40%	486.6	43.18	80.87	Enumerate.py --max-loops=1_000 --block-size=2 --time=10 --lin-steps=0 --no-reverse-engineer --save-freq=10_000
Terry Ligocki	66,029,536	46,119,004	30.15%	167.4	33.05	109.59	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	46,119,004	39,034,142	15.36%	170.1	11.57	75.34	CPS_Filter.py --min-block-size=4 --max-block-size=12 --max-steps=1_000
Terry Ligocki	39,034,142	29,109,512	25.43%	2,221.6	1.24	4.88	CPS_Filter.py --min-block-size=4 --max-block-size=6 --max-steps=10_000
Terry Ligocki	29,109,512	24,536,819	15.71%	384.2	3.31	21.05	Enumerate.py --max-loops=10_000 --block-size=6 --recursive --no-steps --time=0.05 --lin-steps=0 --no-ctl --no-reverse-engineer --save-freq=10_000
Terry Ligocki	24,536,819	22,302,296	9.11%	1,047.5	0.59	6.51	Enumerate.py --max-loops=10_000 --block-size=4 --recursive --no-steps --time=1.00 --lin-steps=0 --no-ctl --no-reverse-engineer --save-freq=10_000

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

Andrew Ducharme ran another pass of "lr_enum_continue" with the maximum number of steps set to 10 million. The holdouts were reduced from ~22.3M TMs to ~20.4M TMs (a 8.72% reduction). The entry in the table below has a rather technical/arcane/cryptic description. This was an effort to capture enough information to rerun that filter in parallel with specific C++ code, lr_enum_continue, and a specific parallel queuing system, Slurm:

(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
	Andrew Ducharme	22,302,296			20,358,011	8.72%			1,350.0	0.40	4.59	lr_enum_continue ${WORK_DIR}chunk_${SLURM_ARRAY_TASK_ID} 10000000 ${WORK_DIR}halt_${SLURM_ARRAY_TASK_ID}.txt ${WORK_DIR}inf_${SLURM_ARRAY_TASK_ID}.txt ${WORK_DIR}unknown_${SLURM_ARRAY_TASK_ID}.txt "" false	Google Drive

Stage 2

Starting from the results of Stage 1, Terry Ligocki ran @mxdys' C++ code, "main.exe", using a variety of its deciders with various parameters. A total of 50 variations were run. The holdouts were reduced from ~20.4M TMs to ~907K TMs (a 95.5% reduction). The details are given in this table, including links to the Google Drive with the holdouts and details of the computation:

(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	20,358,011	19,500,847	4.21%	22.0	10.84	257.42	MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 6 run	Google Drive
Terry Ligocki	19,500,847	18,747,861	3.86%	86.0	2.43	63.01	MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 8 run
Terry Ligocki	18,747,861	4,811,076	74.34%	47.0	82.33	110.75	chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki	4,811,076	2,982,075	38.02%	17.1	29.74	78.22	chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki	2,982,075	2,897,340	2.84%	15.2	1.55	54.64	MitM_CTL RWL_mod sim 1001 maxT 10000 H 8 mod 3 n 6 run
Terry Ligocki	2,897,340	2,850,781	1.61%	16.7	0.77	48.17	chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 30000 NG_n 7 run
Terry Ligocki	2,850,781	2,759,635	3.20%	13.7	1.85	58.01	MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 6 run
Terry Ligocki	2,759,635	1,953,426	29.21%	13.6	16.48	56.42	chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 30000 NG_n 2 run
Terry Ligocki	1,953,426	1,855,545	5.01%	2.4	11.18	223.14	MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 3 n 1 run
Terry Ligocki	1,855,545	1,647,269	11.22%	6.6	8.80	78.40	MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 1 n 4 run
Terry Ligocki	1,647,269	1,608,166	2.37%	3.4	3.20	134.96	chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
Terry Ligocki	1,608,166	1,585,745	1.39%	9.6	0.65	46.35	MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 1 n 12 run
Terry Ligocki	1,585,745	1,555,673	1.90%	5.7	1.47	77.73	chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 10000 NG_n 5 run
Terry Ligocki	1,555,673	1,428,534	8.17%	9.3	3.78	46.31	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run
Terry Ligocki	1,428,534	1,340,964	6.13%	0.8	29.70	484.55	chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 10000 NG_n 1 run
Terry Ligocki	1,340,964	1,286,439	4.07%	0.8	18.40	452.56	chr_LRUH 2 chr_H 2 MitM_CTL NG maxT 3000 NG_n 1 run
Terry Ligocki	1,286,439	1,273,911	0.97%	0.8	4.20	430.88	chr_LRUH 4 chr_H 0 MitM_CTL NG maxT 30000 NG_n 1 run
Terry Ligocki	1,273,911	1,265,198	0.68%	0.8	2.88	420.73	chr_LRUH 3 chr_H 1 MitM_CTL NG maxT 3000 NG_n 2 run
Terry Ligocki	1,265,198	1,258,925	0.50%	0.9	1.99	400.83	chr_LRUH 8 chr_H 6 MitM_CTL NG maxT 30000 NG_n 1 run
Terry Ligocki	1,258,925	1,242,136	1.33%	0.8	5.51	412.84	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 1 tH 0 n 1 run
Terry Ligocki	1,242,136	1,231,731	0.84%	1.0	2.78	331.77	MitM_CTL RWL_mod sim 1001 maxT 3000 H 2 mod 2 n 2 run
Terry Ligocki	1,231,731	1,216,646	1.22%	1.0	4.15	338.72	MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 12 H 0 tH 2 n 2 run
Terry Ligocki	1,216,646	1,214,294	0.19%	0.9	0.76	393.03	MitM_CTL RWL_mod sim 1001 maxT 30000 H 2 mod 3 n 1 run
Terry Ligocki	1,214,294	1,213,431	0.07%	0.9	0.28	391.30	chr_LRUH 4 chr_H 2 MitM_CTL NG maxT 30000 NG_n 2 run
Terry Ligocki	1,213,431	1,211,390	0.17%	1.1	0.52	307.13	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 8 H 1 tH 1 n 1 run
Terry Ligocki	1,211,390	1,209,989	0.12%	1.1	0.35	306.09	chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 100000 NG_n 4 run
Terry Ligocki	1,209,989	1,209,974	0.00%	0.9	0.00	381.42	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 16 H 1 tH 0 n 1 run
Terry Ligocki	1,209,974	1,201,890	0.67%	2.5	0.90	134.19	chr_LRUH 16 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
Terry Ligocki	1,201,890	1,200,086	0.15%	1.3	0.37	248.36	chr_LRUH 10 chr_H 6 MitM_CTL NG maxT 30000 NG_n 1 run
Terry Ligocki	1,200,086	1,199,734	0.03%	1.2	0.08	270.32	chr_asth 0 chr_LRUH 3 chr_H 3 MitM_CTL NG maxT 100000 NG_n 3 run
Terry Ligocki	1,199,734	1,198,893	0.07%	2.3	0.10	147.66	MitM_CTL RWL_mod sim 1001 maxT 10000 H 2 mod 6 n 2 run
Terry Ligocki	1,198,893	1,165,493	2.79%	4.5	2.05	73.44	MitM_CTL RWL_mod sim 1001 maxT 30000 H 4 mod 4 n 1 run
Terry Ligocki	1,165,493	1,153,863	1.00%	9.3	0.35	34.88	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 0 tH 1 n 4 run
Terry Ligocki	1,153,863	1,144,711	0.79%	3.7	0.69	87.51	MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 5 n 2 run
Terry Ligocki	1,144,711	1,127,789	1.48%	7.9	0.60	40.26	chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 30000 NG_n 3 run
Terry Ligocki	1,127,789	1,124,762	0.27%	4.7	0.18	66.75	MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 0 tH 1 n 8 run
Terry Ligocki	1,124,762	1,117,226	0.67%	5.6	0.37	55.36	MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 12 H 0 tH 1 n 2 run
Terry Ligocki	1,117,226	1,109,057	0.73%	7.7	0.30	40.49	chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 100000 NG_n 3 run
Terry Ligocki	1,109,057	1,083,097	2.34%	11.4	0.63	27.06	chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 30000 NG_n 5 run
Terry Ligocki	1,083,097	1,077,833	0.49%	11.2	0.13	26.81	chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 100000 NG_n 4 run
Terry Ligocki	1,077,833	1,066,795	1.02%	24.1	0.13	12.40	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 2 tH 1 n 2 run
Terry Ligocki	1,066,795	1,039,229	2.58%	52.6	0.15	5.64	chr_LRUH 14 chr_H 6 MitM_CTL NG maxT 100000 NG_n 11 run
Terry Ligocki	1,039,229	1,019,286	1.92%	43.5	0.13	6.63	MitM_CTL RWL_mod sim 1001 maxT 100000 H 12 mod 1 n 3 run
Terry Ligocki	1,019,286	993,556	2.52%	66.8	0.11	4.24	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 8 H 2 tH 1 n 6 run
Terry Ligocki	993,556	985,718	0.79%	78.3	0.03	3.53	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 1 tH 1 n 8 run
Terry Ligocki	985,718	981,095	0.47%	83.7	0.02	3.27	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 1 tH 0 n 9 run
Terry Ligocki	981,095	975,912	0.53%	79.4	0.02	3.43	MitM_CTL RWL_mod sim 1001 maxT 100000 H 16 mod 1 n 8 run
Terry Ligocki	975,912	974,180	0.18%	84.6	0.01	3.20	MitM_CTL RWL_mod sim 1001 maxT 100000 H 16 mod 4 n 8 run
Terry Ligocki	974,180	971,254	0.30%	96.9	0.01	2.79	MitM_CTL RWL_mod sim 1001 maxT 100000 H 12 mod 1 n 12 run
Terry Ligocki	971,254	970,101	0.12%	105.6	0.00	2.56	MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 12 H 0 tH 0 n 18 run

Stage 3

Starting from the results of Stage 2, Andrew Ducharme ran "lr_enum_continue" with the maximum number of steps set to 100 million, then "Enumerate.py" with various parameters. A total of 6 Enumerate variations were run. The holdouts were reduced from ~970K TMs to ~870K TMs (a 10.31% reduction). The details are given in this table, including links to the Google Drive with the holdouts and details of the computation:

(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$
Andrew Ducharme	970,101	939,447	3.16%	--	--	--	lr_enum_continue 100_000_000 steps	Google Drive
Andrew Ducharme	895,813	889,838	0.67%	609.3	0.00	0.41	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=8 --no-ctl --lin-steps=0 --time=4 --force --save-freq=1000
Andrew Ducharme	889,838	880,278	1.07%	1,638.9	0.00	0.15	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=12 --no-ctl --lin-steps=0 --force --save-freq=1000
Andrew Ducharme	880,278	877,485	0.32%	1,885.5	0.00	0.13	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=6 --no-ctl --lin-steps=0 --force --save-freq=1000
Andrew Ducharme	877,485	875,062	0.28%	2,068.8	0.00	0.12	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=5 --no-ctl --lin-steps=0 --force --save-freq=1000
Andrew Ducharme	875,062	873,469	0.18%	1,785.4	0.00	0.14	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=7 --no-ctl --lin-steps=0 --force --save-freq=1000
Andrew Ducharme	873,469	870,085	0.39%	9,270.0	0.00	0.03	Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=2 --tape-limit=500 --time=120 --no-ctl --lin-steps=0 --force --save-freq=1000

The total time spent on the lr_enum_continue computation was not recorded.