BB(2,6): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
ADucharme (talk | contribs)
282 edits
→Top Halters: added Peacemaker's 10^^20k 2x6 halter
Tjligocki (talk | contribs)
249 edits
Added the filled out table to the "Phase 1" section.
Line 94: Line 94:


== Phase 1 ==
== 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,278M were holdout TMs. This was reduced to ~22M holdout TMs (a 99.02% reduction). The details will be given in this table:
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 last 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 very specific C++ code, lr_enum_continue, and a very specific parallel queuing system, Slurm:


(done to reduce column size:
(done to reduce column size:
Line 111: Line 111:
!rowspan="2" |Data
!rowspan="2" |Data
|-
|-
!Input
|style="text-align:left" |Terry Ligocki
!Output
|2,278,655,696
!<math>*^3</math>
|2,109,114,609
!<math>*^4</math>
|7.44%
|40.9
|1,150.90
|15,468.23
|style="text-align:left" |Reverse_Engineer_Filter.py
|style="text-align:left" |[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive]
|-
|-
|style="text-align:left" |'''---'''
|style="text-align:left" |Terry Ligocki
|'''---'''
|2,109,114,609
|'''---'''
|683,067,538
|'''---'''
|67.61%
|'''---'''
|452.8
|'''---'''
|874.77
|'''---'''
|1,293.79
|style="text-align:left" |'''---'''
|style="text-align:left" |CPS_Filter.py --block-size=1
|-
|style="text-align:left" |Terry Ligocki
|683,067,538
|210,993,434
|69.11%
|396.4
|330.85
|478.72
|style="text-align:left" |CPS_Filter.py --block-size=2
|-
|style="text-align:left" |Terry Ligocki
|210,993,434
|141,680,232
|32.85%
|273.9
|70.29
|213.97
|style="text-align:left" |CPS_Filter.py --block-size=3 --max_steps=10_000
|-
|style="text-align:left" |Terry Ligocki
|141,680,232
|66,029,536
|53.40%
|486.6
|43.18
|80.87
|style="text-align:left" |Enumerate.py --max-loops=1_000 --block-size=2 --time=10 --lin-steps=0 --no-reverse-engineer --save-freq=10_000
|-
|style="text-align:left" |Terry Ligocki
|66,029,536
|46,119,004
|30.15%
|167.4
|33.05
|109.59
|style="text-align:left" |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
|-
|style="text-align:left" |Terry Ligocki
|46,119,004
|39,034,142
|15.36%
|170.1
|11.57
|75.34
|style="text-align:left" |CPS_Filter.py --min-block-size=4 --max-block-size=12 --max-steps=1_000
|-
|style="text-align:left" |Terry Ligocki
|39,034,142
|29,109,512
|25.43%
|2,221.6
|1.24
|4.88
|style="text-align:left" |CPS_Filter.py --min-block-size=4 --max-block-size=6 --max-steps=10_000
|-
|style="text-align:left" |Terry Ligocki
|29,109,512
|24,536,819
|15.71%
|384.2
|3.31
|21.05
|style="text-align:left" |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
|-
|style="text-align:left" |Terry Ligocki
|24,536,819
|22,302,296
|9.11%
|1,047.5
|0.59
|6.51
|style="text-align:left" |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
|-
|style="text-align:left" |Terry Ligocki
|22,302,296
|20,358,011
|8.72%
|1,350.0
|0.40
|4.59
|style="text-align:left" |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
|}
|}


Revision as of 18:50, 8 October 2025

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)>Σ(2,6)>10↑↑10↑↑1010115>10↑↑↑3

Top Halters

The scores are given using Knuth's up-arrow notation with an extension to decimal tetration[1]. 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 last 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 very specific C++ code, lr_enum_continue, and a very 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
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
Terry Ligocki 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

Phase 2

Starting from Terry Ligocki's holdouts list of 22,302,296 TMs, additional filtering has been performed:

(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 22,302,296 20,246,662 9.2% 23.0 24.80 269.09 MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 6 run Google Drive
Terry Ligocki 20,246,662 19,134,631 5.5% 83.4 3.71 67.46 MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 8 run
Terry Ligocki 19,134,631 5,443,318 71.6% 46.6 81.69 114.17 chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki 5,443,318 3,400,118 37.5% 16.3 34.87 92.90 chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 10000 NG_n 3 run
Terry Ligocki 3,400,118 3,303,416 2.8% 14.1 1.90 66.82 MitM_CTL RWL_mod sim 1001 maxT 10000 H 8 mod 3 n 6 run
Terry Ligocki 3,303,416 3,249,427 1.6% 16.5 0.91 55.59 chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 30000 NG_n 7 run
Terry Ligocki 3,249,427 3,155,741 2.9% 13.4 1.94 67.25 MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 6 run
Terry Ligocki 3,155,741 2,246,891 28.8% 14.1 17.93 62.24 chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 30000 NG_n 2 run
Terry Ligocki 2,246,891 2,143,803 4.6% 7.5 3.82 83.19 MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 3 n 1 run
Terry Ligocki 2,143,803 1,938,663 9.6% 7.5 7.58 79.21 MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 1 n 4 run
Terry Ligocki 1,938,663 1,885,153 2.8% 7.5 1.98 71.72 chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
Terry Ligocki 1,885,153 1,848,887 1.9% 10.5 0.96 49.68 MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 1 n 12 run
Terry Ligocki 1,848,887 1,816,027 1.8% 7.6 1.20 67.77 chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 10000 NG_n 5 run
Terry Ligocki 1,816,027 1,688,951 7.0% 10.4 3.40 48.66 MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run

References

  1. ↑ Shawn Ligocki. 2022. "Extending Up-arrow Notation"
Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=BB(2,6)&oldid=4416"