BB(2,6): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older editNewer edit →
VisualWikitext
Tjligocki (talk | contribs)
410 edits
m →Stage 3: Minor table change
Tjligocki (talk | contribs)
410 edits
m →Stage 4: Cleaned up table a bit
Line 803: Line 803:
|364.10
|364.10
|5,666.72
|5,666.72
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 1 tH 1 n 2
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 1 tH 1 n 2
| rowspan="30" |[https://drive.google.com/drive/folders/18njhmOzRc67zCmVuLd0aDxl6ETBhL1gy?usp=sharing Google Drive]
|style="text-align:center" rowspan="44" |[https://drive.google.com/drive/folders/18njhmOzRc67zCmVuLd0aDxl6ETBhL1gy?usp=sharing Google Drive]
|-
|-
|811,301
|811,301
Line 812: Line 812:
|9.03
|9.03
|1,413.42
|1,413.42
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 3 H 1 tH 1 n 2
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 3 H 1 tH 1 n 2
|-
|-
|806,119
|806,119
Line 820: Line 820:
|35.21
|35.21
|408.78
|408.78
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 1 tH 1 n 2
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 1 tH 1 n 2
|-
|-
|736,690
|736,690
Line 828: Line 828:
|5.81
|5.81
|23,021.56
|23,021.56
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 1 H 1 tH 1 n 1
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 1 H 1 tH 1 n 1
|-
|-
|736,504
|736,504
Line 836: Line 836:
|5.71
|5.71
|3,540.88
|3,540.88
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 0 tH 0 n 2
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 0 tH 0 n 2
|-
|-
|735,317
|735,317
Line 844: Line 844:
|1.30
|1.30
|599.28
|599.28
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 2
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 2
|-
|-
|733,717
|733,717
Line 852: Line 852:
|4.43
|4.43
|54.32
|54.32
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 4
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 4
|-
|-
|673,920
|673,920
Line 860: Line 860:
| ---
| ---
| ---
| ---
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 6 H 2 tH 2 n 4
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 6 H 2 tH 2 n 4
|-
|-
|652,828
|652,828
Line 868: Line 868:
| ---
| ---
| ---
| ---
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 8 H 2 tH 2 n 4
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 8 H 2 tH 2 n 4
|-
|-
|645,264
|645,264
Line 876: Line 876:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 100000 LRUH 10 H 2 tH 2 n 10
|style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 10 H 2 tH 2 n 10
|-
|-
|641,388
|641,388
Line 884: Line 884:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 10 H 1 tH 2 n 10
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 10 H 1 tH 2 n 10
|-
|-
|635,505
|635,505
Line 892: Line 892:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 2 H 0 tH 0 n [3-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 2 H 0 tH 0 n [3-10]
|-
|-
|616,639
|616,639
Line 900: Line 900:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 3 H 0 tH 0 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 3 H 0 tH 0 n [1-10]
|-
|-
|592,039
|592,039
Line 908: Line 908:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 3 H [0-1] tH [0-1] n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 3 H [0-1] tH [0-1] n [1-10]
|-
|-
|576,938
|576,938
Line 916: Line 916:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 4 H 0 tH 0 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 4 H 0 tH 0 n [1-10]
|-
|-
|572,963
|572,963
Line 924: Line 924:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 4 H 2 tH 0 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 4 H 2 tH 0 n [1-10]
|-
|-
|567,971
|567,971
Line 932: Line 932:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 6 H 0 tH 0 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 6 H 0 tH 0 n [1-10]
|-
|-
|566,096
|566,096
Line 940: Line 940:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 0 tH [0,2] n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 8 H 0 tH [0,2] n [1-10]
|-
|-
|564,290
|564,290
Line 948: Line 948:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 1 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 1 n [1-10]
|-
|-
|559,553
|559,553
Line 956: Line 956:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 2 n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 2 n [1-10]
|-
|-
|558,039
|558,039
Line 964: Line 964:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH [12,16] H [0-2] tH [0-2] n [1-10]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH [12,16] H [0-2] tH [0-2] n [1-10]
|-
|-
|556,814
|556,814
Line 972: Line 972:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH [1-3]
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH [1-3]
|-
|-
|554,479
|554,479
Line 980: Line 980:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 4
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 4
|-
|-
|551,586
|551,586
Line 988: Line 988:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 5
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 5
|-
|-
|548,993
|548,993
Line 996: Line 996:
| ---
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 6 and 8
|style="text-align:left" |FAR CPS_LRU maxT 1000000 LRUH 6 and 8
|-
|-
|545,005
|545,005
Line 1,004: Line 1,004:
|0.00
|0.00
|0.022
|0.022
|Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=96 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|style="text-align:left" |Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=96 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|-
|-
|542,325
|542,325
Line 1,012: Line 1,012:
|0.00
|0.00
|0.017
|0.017
|Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=2 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|style="text-align:left" |Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=2 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|-
|-
|537,393
|537,393
Line 1,020: Line 1,020:
|0.00
|0.00
|0.017
|0.017
|Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=3 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|style="text-align:left" |Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=3 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|-
|-
|536,112
|536,112
Line 1,028: Line 1,028:
| ---
| ---
| ---
| ---
|Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=7 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|style="text-align:left" |Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=7 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
|-
|-
|533,764
|533,764
Line 1,036: Line 1,036:
| ---
| ---
| ---
| ---
|chr_LRUH 1 chr_H 0 MitM_CTL NG maxT 1 s NG_n [1-10]
|style="text-align:left" |
chr_LRUH 1 chr_H 0 MitM_CTL NG maxT 1 s NG_n [1-10]
chr_LRUH 2 chr_H 1 MitM_CTL NG maxT 1 s NG_n [1-10]
chr_LRUH 2 chr_H 1 MitM_CTL NG maxT 1 s NG_n [1-10]
chr_LRUH 3 chr_H 2 MitM_CTL NG maxT 1 s NG_n [1-10]
chr_LRUH 3 chr_H 2 MitM_CTL NG maxT 1 s NG_n [1-10]
Line 1,054: Line 1,055:
| ---
| ---
| ---
| ---
|Inductive_inf.v --maxT 1000 --arithseq --exploop
|style="text-align:left" |Inductive_inf.v --maxT 1000 --arithseq --exploop
|-
|-
|502,532
|502,532
Line 1,062: Line 1,063:
| ---
| ---
| ---
| ---
|chr_LRUH [8,10,12,16] chr_H [chr_LRUH-4] MitM_CTL NG maxT 1 s NG_n [1-10]
|style="text-align:left" |chr_LRUH [8,10,12,16] chr_H [chr_LRUH-4] MitM_CTL NG maxT 1 s NG_n [1-10]
|-
|-
|501,914
|501,914
Line 1,070: Line 1,071:
| ---
| ---
| ---
| ---
|Inductive_inf.v --maxT 10000 --exploop
|style="text-align:left" |Inductive_inf.v --maxT 10000 --exploop
|-
|-
|439,120
|439,120
Line 1,078: Line 1,079:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 1000000 H [1-2] mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 1000000 H [1-2] mod [1-6] n [1-10]
|-
|-
|437,729
|437,729
Line 1,086: Line 1,087:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 1000000 H [3] mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 1000000 H [3] mod [1-6] n [1-10]
|-
|-
|432,360
|432,360
Line 1,094: Line 1,095:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 1000000 H [4] mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 1000000 H [4] mod [1-6] n [1-10]
|-
|-
|424,733
|424,733
Line 1,102: Line 1,103:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 100000 H [6] mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 100000 H [6] mod [1-6] n [1-10]
|-
|-
|419,045
|419,045
Line 1,110: Line 1,111:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 100000 H [8] mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 100000 H [8] mod [1-6] n [1-10]
|-
|-
|418,127
|418,127
Line 1,118: Line 1,119:
| ---
| ---
| ---
| ---
|chr_LRUH 12 chr_H 6 MitM_CTL NG maxT 1000000 NG_n [1-10]
|style="text-align:left" |
chr_LRUH 12 chr_H 6 MitM_CTL NG maxT 1000000 NG_n [1-10]
chr_LRUH 13 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10]
chr_LRUH 13 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10]
chr_LRUH 14 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10]
chr_LRUH 14 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10]
Line 1,130: Line 1,132:
| ---
| ---
| ---
| ---
|chr_LRUH [17-22] chr_H 12 MitM_CTL NG maxT 1000000 NG_n [1-10]
|style="text-align:left" |chr_LRUH [17-22] chr_H 12 MitM_CTL NG maxT 1000000 NG_n [1-10]
|-
|-
|415,414
|415,414
Line 1,138: Line 1,140:
| ---
| ---
| ---
| ---
|chr_asth 0 chr_LRUH [x] chr_H [x] MitM_CTL NG maxT 1000000 NG_n [1-16], x=[8,12,16,24,32]
|style="text-align:left" |chr_asth 0 chr_LRUH [x] chr_H [x] MitM_CTL NG maxT 1000000 NG_n [1-16], x=[8,12,16,24,32]
|-
|-
|414,009
|414,009
Line 1,146: Line 1,148:
| ---
| ---
| ---
| ---
|chr_LRUH [2-6,8,12,14,16,28] chr_LRUn 2 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
|style="text-align:left" |chr_LRUH [2-6,8,12,14,16,28] chr_LRUn 2 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
|-
|-
|413,513
|413,513
Line 1,154: Line 1,156:
| ---
| ---
| ---
| ---
|chr_LRUH [3,7,12,14,16,20,28] chr_LRUn 3 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
|style="text-align:left" |chr_LRUH [3,7,12,14,16,20,28] chr_LRUn 3 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
|-
|-
|413,207
|413,207
Line 1,162: Line 1,164:
| ---
| ---
| ---
| ---
|FAR RWL_mod maxT 1000000 H 5 mod [1-6] n [1-10]
|style="text-align:left" |FAR RWL_mod maxT 1000000 H 5 mod [1-6] n [1-10]
|}
|}


Revision as of 22:04, 29 June 2026

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
1RB2LA5LB0RA1RA3LB_1LA4LA3LB3RB3RB1RZ (bbch) 10 ↑↑ 23.9964 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

All decimal places are truncated.

Phase 1

The initial phase of enumeration and reduction of holdouts took place in November 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 10 Enumerate variations were run. The holdouts were reduced from ~970K TMs to ~867K TMs (a 10.63% 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
939,447 903,224 3.86% 440.3 0.03 0.59 Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=4 --no-ctl --lin-steps=0 --time=2 --force --save-freq=1000
903,224 895,813 0.82% 647.7 0.00 0.39 Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=3 --no-ctl --lin-steps=0 --time=3 --force --save-freq=1000
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
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
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
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
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
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
870,085 869,001 0.12% 4,498.3 0.00 0.05 Enumerate.py --no-steps --exp-linear-rules --max_loops=10_000_000 --block-mult=60 --tape-limit=5000 --no-ctl --lin-steps=0 --force --save-freq=1000
869,001 867,008 0.23% 3997.4 0.00 0.06 Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=9 --tape-limit=5000 --max-steps-per-macro=100_000 --lin-steps=0 --no-ctl --force --save-freq=250

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

Stage 4

Following the release of @mxdys's implementation of FAR deciders in C++, these deciders were applied to the 2x6 holdouts by Andrew Ducharme. The details are given in this table, including links to the Google Drive with the holdouts and solved TMs per decider:

(done to reduce column size: *1= % Reduced, *2= Compute Time (core-hours), *3= Decided, *4= Processed)

Holdout TMs *1 *2 TMs/sec/core Description Data
Input Output *3 *4
867,008 811,301 6.43% 0.043 364.10 5,666.72 FAR CPS_LRU maxT 100000 LRUH 2 H 1 tH 1 n 2 Google Drive
811,301 806,119 0.64% 0.159 9.03 1,413.42 FAR CPS_LRU maxT 100000 LRUH 3 H 1 tH 1 n 2
806,119 736,690 8.61% 0.548 35.21 408.78 FAR CPS_LRU maxT 100000 LRUH 4 H 1 tH 1 n 2
736,690 736,504 0.03% 0.009 5.81 23,021.56 FAR CPS_LRU maxT 100000 LRUH 1 H 1 tH 1 n 1
736,504 735,317 0.16% 0.058 5.71 3,540.88 FAR CPS_LRU maxT 100000 LRUH 2 H 0 tH 0 n 2
735,317 733,717 0.22% 0.341 1.30 599.28 FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 2
733,717 673,920 8.15% 3.8 4.43 54.32 FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 4
673,920 652,828 3.13% ~10 --- --- FAR CPS_LRU maxT 100000 LRUH 6 H 2 tH 2 n 4
652,828 645,264 1.16% ~12 --- --- FAR CPS_LRU maxT 100000 LRUH 8 H 2 tH 2 n 4
645,264 641,388 0.60% ~15 --- --- FAR CPS_LRU maxT 100000 LRUH 10 H 2 tH 2 n 10
641,388 635,505 0.92% ~200 --- --- FAR CPS_LRU maxT 1000000 LRUH 10 H 1 tH 2 n 10
635,505 616,639 2.97% --- --- --- FAR CPS_LRU maxT 1000000 LRUH 2 H 0 tH 0 n [3-10]
616,639 592,039 3.99% ~700 --- --- FAR CPS_LRU maxT 1000000 LRUH 3 H 0 tH 0 n [1-10]
592,039 576,938 2.55% ~800 --- --- FAR CPS_LRU maxT 1000000 LRUH 3 H [0-1] tH [0-1] n [1-10]
576,938 572,963 0.69% ~1,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 4 H 0 tH 0 n [1-10]
572,963 567,971 0.87% ~1,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 4 H 2 tH 0 n [1-10]
567,971 566,096 0.33% ~1,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 6 H 0 tH 0 n [1-10]
566,096 564,290 0.32% ~1,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 0 tH [0,2] n [1-10]
564,290 559,553 0.84% ~1,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 1 n [1-10]
559,553 558,039 0.27% ~900 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 2 n [1-10]
558,039 556,814 0.22% ~14,000 --- --- FAR CPS_LRU maxT 1000000 LRUH [12,16] H [0-2] tH [0-2] n [1-10]
556,814 554,479 0.42% ~3,600 --- --- FAR CPS_LRU maxT 1000000 LRUH [1-3]
554,479 551,586 0.52% ~5000 --- --- FAR CPS_LRU maxT 1000000 LRUH 4
551,586 548,993 0.47% ~13,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 5
548,993 545,005 0.73% ~57,000 --- --- FAR CPS_LRU maxT 1000000 LRUH 6 and 8
545,005 542,325 0.49% 6851.2 0.00 0.022 Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=96 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
542,325 537,393 0.91% 9032.1 0.00 0.017 Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=2 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
537,393 536,112 0.24% 8969.4 0.00 0.017 Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=3 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
536,112 533,764 0.43% 8778.5 --- --- Enumerate.py -r --no-steps --exp-linear-rules --max-loops=100_000_000 --block-mult=7 --tape-limit=50_000 --max-steps-per-macro=1_000_000 --time=60 --lin-steps=0 --no-ctl
533,764 527,232 1.22% ~3500 --- ---

chr_LRUH 1 chr_H 0 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 2 chr_H 1 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 3 chr_H 2 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 5 chr_H 4 MitM_CTL NG maxT 1 s NG_n [1-15] chr_LRUH 7 chr_H 6 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 9 chr_H 8 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 11 chr_H 8 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 12 chr_H 10 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 13 chr_H 12 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 1 s NG_n [1-10] chr_LRUH 15 chr_H 12 MitM_CTL NG maxT 1 s NG_n [1-10]

527,232 502,532 4.68% 4.1 --- --- Inductive_inf.v --maxT 1000 --arithseq --exploop
502,532 501,914 0.12% ~1700 --- --- chr_LRUH [8,10,12,16] chr_H [chr_LRUH-4] MitM_CTL NG maxT 1 s NG_n [1-10]
501,914 439,120 12.51% 42.87 --- --- Inductive_inf.v --maxT 10000 --exploop
439,120 437,729 0.32% ~2000 --- --- FAR RWL_mod maxT 1000000 H [1-2] mod [1-6] n [1-10]
437,729 432,360 1.23% ~2800 --- --- FAR RWL_mod maxT 1000000 H [3] mod [1-6] n [1-10]
432,360 424,733 1.76% ~3200 --- --- FAR RWL_mod maxT 1000000 H [4] mod [1-6] n [1-10]
424,733 419,045 1.34% ~450 --- --- FAR RWL_mod maxT 100000 H [6] mod [1-6] n [1-10]
419,045 418,127 0.22% ~600 --- --- FAR RWL_mod maxT 100000 H [8] mod [1-6] n [1-10]
418,127 416,677 0.35% ~2800 --- ---

chr_LRUH 12 chr_H 6 MitM_CTL NG maxT 1000000 NG_n [1-10] chr_LRUH 13 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10] chr_LRUH 14 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10] chr_LRUH 15 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10] chr_LRUH 16 chr_H 8 MitM_CTL NG maxT 1000000 NG_n [1-10]

416,677 415,414 0.30% ~4300 --- --- chr_LRUH [17-22] chr_H 12 MitM_CTL NG maxT 1000000 NG_n [1-10]
415,414 414,009 0.34% ~6600 --- --- chr_asth 0 chr_LRUH [x] chr_H [x] MitM_CTL NG maxT 1000000 NG_n [1-16], x=[8,12,16,24,32]
414,009 413,513 0.12% ? --- --- chr_LRUH [2-6,8,12,14,16,28] chr_LRUn 2 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
413,513 413,207 0.07% ? --- --- chr_LRUH [3,7,12,14,16,20,28] chr_LRUn 3 MitM_CTL NG maxT 1000000 NG_n [1-4,6,8,12,16]
413,207 412,086 0.27% ? --- --- FAR RWL_mod maxT 1000000 H 5 mod [1-6] n [1-10]

References

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