BB(2,6): Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
← Older edit
VisualWikitext
→Top Halters: fix formatting
ADucharme (talk | contribs)
304 edits
m →Phase 2: left-align new decider columns
 
(20 intermediate revisions by 4 users not shown)
Line 4: Line 4:


== Top Halters ==
== Top Halters ==
{{Incomplete List}}
The scores are given using [[wikipedia:Knuth's_up-arrow_notation|Knuth's up-arrow notation]] with an extension to decimal tetration<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>. The 20 highest known scoring machines are:
The scores are given using [[wikipedia:Knuth's_up-arrow_notation|Knuth's up-arrow notation]] with an extension to decimal tetration<ref>Shawn Ligocki. 2022. [https://www.sligocki.com/2022/06/25/ext-up-notation.html "Extending Up-arrow Notation"]</ref>. The highest known scoring machines are:
{| class="wikitable"
{| class="wikitable"
|+
|+
Line 15: Line 14:
|10 ↑↑↑ 3
|10 ↑↑↑ 3
|Pavel Kropitz
|Pavel Kropitz
|-
|{{TM|1RB2LA1RZ1RB5RB0RB_2LA4RA3LB5LB5RA4LB|halt}}
|10 ↑↑ 19892.08
|Peacemaker II
|-
|-
|{{TM|1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ|halt}}
|{{TM|1RB3LA4LB0RB1RA3LA_2LA2RA4LA1RA5RB1RZ|halt}}
Line 52: Line 55:
|Shawn Ligocki
|Shawn Ligocki
|-
|-
|{{TM|1RB0RA3RB0LB5LA2LA_2LA4LB1RA3LB5LB1RZ}|halt}}
|{{TM|1RB0RA3RB0LB5LA2LA_2LA4LB1RA3LB5LB1RZ|halt}}
|10 ↑↑ 17.53
|10 ↑↑ 17.53
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RA4LB5RA5LB4RA_2LA1RZ1RB2LA5LA0LA}|halt}}
|{{TM|1RB3RA4LB5RA5LB4RA_2LA1RZ1RB2LA5LA0LA|halt}}
|10 ↑↑ 17.08
|10 ↑↑ 17.08
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RA4LA1LA0LA1RZ_2LA0LB1RA1LB5LB2RA}|halt}}
|{{TM|1RB3RA4LA1LA0LA1RZ_2LA0LB1RA1LB5LB2RA|halt}}
|10 ↑↑ 15.44
|10 ↑↑ 15.44
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ2LA}|halt}}
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ2LA|halt}}
|10 ↑↑ 14.35
|10 ↑↑ 14.35
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ3RA}|halt}}
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ3RA|halt}}
|10 ↑↑ 14.17
|10 ↑↑ 14.17
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ1LA}|halt}}
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ1LA|halt}}
|10 ↑↑ 14.05
|10 ↑↑ 14.05
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ0RA}|halt}}
|{{TM|1RB3RB5LA1LA2RA3LA_2LA3RA2LB4LB1RZ0RA|halt}}
|10 ↑↑ 13.69
|10 ↑↑ 13.69
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB3LA3RA4LB2LB0LA_2LA5LB2RB0RA0RA1RZ}|halt}}
|{{TM|1RB3LA3RA4LB2LB0LA_2LA5LB2RB0RA0RA1RZ|halt}}
|10 ↑↑ 12.42
|10 ↑↑ 12.42
|Andrew Ducharme
|Andrew Ducharme
|-
|-
|{{TM|1RB0LB4LA2RA2RB1LB_2LA4LA3LB5LA1RA1RZ}|halt}}
|{{TM|1RB0LB4LA2RA2RB1LB_2LA4LA3LB5LA1RA1RZ|halt}}
|10 ↑↑ 11.70
|10 ↑↑ 11.70
|Andrew Ducharme
|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:
<math>*^1</math>= % Reduced,
<math>*^2</math>= Runtime (hours),
<math>*^3</math>= Decided,
<math>*^4</math>= Processed)
{| class="wikitable sortable" style="text-align: right"
!rowspan="2" |Done by
!colspan="2" |Holdout TMs
!rowspan="2" |<math>*^1</math>
!rowspan="2" |<math>*^2</math>
!colspan="2" |TMs/sec/core
!rowspan="2" |Description
!rowspan="2" |Data
|-
|-
|{{TM|1RB2LA1RA1RA5LB1RZ_1LA4RB3RB4LB0RB0RA}|halt}}
|style="text-align:left" |Terry Ligocki
|10 ↑↑ 10.39
|2,278,655,696
|Andrew Ducharme
|2,109,114,609
|7.44%
|40.9
|1,150.90
|15,468.23
|style="text-align:left" |Reverse_Engineer_Filter.py
|style="text-align:left", rowspan="100" |[https://drive.google.com/drive/folders/1p9b5g-Id3WEMUYIwEnaKWRBGIW66ADjM?usp=drive_link Google Drive]
|-
|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" |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
|}
 
== 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:
<math>*^1</math>= % Reduced,
<math>*^2</math>= Runtime (hours),
<math>*^3</math>= Decided,
<math>*^4</math>= Processed)
 
{| class="wikitable sortable" style="text-align: right"
!rowspan="2" |Done by
!colspan="2" |Holdout TMs
!rowspan="2" |<math>*^1</math>
!rowspan="2" |<math>*^2</math>
!colspan="2" |TMs/sec/core
!rowspan="2" |Description
!rowspan="2" |Data
|-
|style="text-align:left" |Andrew Ducharme
|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
|style="text-align:left" rowspan="50"|[https://drive.google.com/drive/folders/1TsSpW27x3LBlu5qmk-cjzCJzgo_3ehyT?usp=drive_link Google Drive]
|}
|}
All decimal places are truncated.


== Filtering ==
=== Stage 2 ===
Starting from Terry Ligocki's [[holdouts list]] of 22,302,296 TMs, additional filtering has been performed:
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:
(done to reduce column size:
Line 118: Line 259:
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|22,302,296
|20,358,011
|20,246,662
|19,500,847
|9.2%
|4.21%
|23.0
|22.0
|24.80
|10.84
|269.09
|257.42
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 6 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 3000 H 6 mod 2 n 6 run
|rowspan="100" |[https://drive.google.com/drive/folders/1TsSpW27x3LBlu5qmk-cjzCJzgo_3ehyT?usp=share_link Google Drive]
|style="text-align:left" rowspan="50"|[https://drive.google.com/drive/folders/1TsSpW27x3LBlu5qmk-cjzCJzgo_3ehyT?usp=drive_link Google Drive]
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|20,246,662
|19,500,847
|19,134,631
|18,747,861
|5.5%
|3.86%
|83.4
|86.0
|3.71
|2.43
|67.46
|63.01
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 8 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 8 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|19,134,631
|18,747,861
|5,443,318
|4,811,076
|71.6%
|74.34%
|46.6
|47.0
|81.69
|82.33
|114.17
|110.75
|style="text-align:left" |chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
|style="text-align:left" |chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 10000 NG_n 3 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|5,443,318
|4,811,076
|3,400,118
|2,982,075
|37.5%
|38.02%
|16.3
|17.1
|34.87
|29.74
|92.90
|78.22
|style="text-align:left" |chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 10000 NG_n 3 run
|style="text-align:left" |chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 10000 NG_n 3 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|3,400,118
|2,982,075
|3,303,416
|2,897,340
|2.8%
|2.84%
|14.1
|15.2
|1.90
|1.55
|66.82
|54.64
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 8 mod 3 n 6 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 8 mod 3 n 6 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|3,303,416
|2,897,340
|3,249,427
|2,850,781
|1.6%
|1.61%
|16.5
|16.7
|0.91
|0.77
|55.59
|48.17
|style="text-align:left" |chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 30000 NG_n 7 run
|style="text-align:left" |chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 30000 NG_n 7 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|3,249,427
|2,850,781
|3,155,741
|2,759,635
|2.9%
|3.20%
|13.4
|13.7
|1.94
|1.85
|67.25
|58.01
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 6 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 2 n 6 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|3,155,741
|2,759,635
|2,246,891
|1,953,426
|28.8%
|29.21%
|14.1
|13.6
|17.93
|16.48
|62.24
|56.42
|style="text-align:left" |chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 30000 NG_n 2 run
|style="text-align:left" |chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 30000 NG_n 2 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|2,246,891
|1,953,426
|2,143,803
|1,855,545
|4.6%
|5.01%
|7.5
|2.4
|3.82
|11.18
|83.19
|223.14
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 3 n 1 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 3 n 1 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|2,143,803
|1,855,545
|1,938,663
|1,647,269
|9.6%
|11.22%
|7.5
|6.6
|7.58
|8.80
|79.21
|78.40
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 1 n 4 run
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 8 H 1 tH 1 n 4 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|1,938,663
|1,647,269
|1,885,153
|1,608,166
|2.8%
|2.37%
|7.5
|3.4
|1.98
|3.20
|71.72
|134.96
|style="text-align:left" |chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
|style="text-align:left" |chr_LRUH 14 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|1,885,153
|1,608,166
|1,848,887
|1,585,745
|1.9%
|1.39%
|10.5
|9.6
|0.96
|0.65
|49.68
|46.35
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 1 n 12 run
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 3 mod 1 n 12 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|1,848,887
|1,585,745
|1,816,027
|1,555,673
|1.8%
|1.90%
|7.6
|5.7
|1.20
|1.47
|67.77
|77.73
|style="text-align:left" |chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 10000 NG_n 5 run
|style="text-align:left" |chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 10000 NG_n 5 run
|-
|-
|style="text-align:left" |Terry Ligocki
|style="text-align:left" |Terry Ligocki
|1,816,027
|1,555,673
|1,688,951
|1,428,534
|7.0%
|8.17%
|10.4
|9.3
|3.40
|3.78
|48.66
|46.31
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 2 tH 0 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,428,534
|1,340,964
|6.13%
|0.8
|29.70
|484.55
|style="text-align:left" |chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 10000 NG_n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,340,964
|1,286,439
|4.07%
|0.8
|18.40
|452.56
|style="text-align:left" |chr_LRUH 2 chr_H 2 MitM_CTL NG maxT 3000 NG_n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,286,439
|1,273,911
|0.97%
|0.8
|4.20
|430.88
|style="text-align:left" |chr_LRUH 4 chr_H 0 MitM_CTL NG maxT 30000 NG_n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,273,911
|1,265,198
|0.68%
|0.8
|2.88
|420.73
|style="text-align:left" |chr_LRUH 3 chr_H 1 MitM_CTL NG maxT 3000 NG_n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,265,198
|1,258,925
|0.50%
|0.9
|1.99
|400.83
|style="text-align:left" |chr_LRUH 8 chr_H 6 MitM_CTL NG maxT 30000 NG_n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,258,925
|1,242,136
|1.33%
|0.8
|5.51
|412.84
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 1 tH 0 n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,242,136
|1,231,731
|0.84%
|1.0
|2.78
|331.77
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 3000 H 2 mod 2 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,231,731
|1,216,646
|1.22%
|1.0
|4.15
|338.72
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 3000 LRUH 12 H 0 tH 2 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,216,646
|1,214,294
|0.19%
|0.9
|0.76
|393.03
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 30000 H 2 mod 3 n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,214,294
|1,213,431
|0.07%
|0.9
|0.28
|391.30
|style="text-align:left" |chr_LRUH 4 chr_H 2 MitM_CTL NG maxT 30000 NG_n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,213,431
|1,211,390
|0.17%
|1.1
|0.52
|307.13
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 8 H 1 tH 1 n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,211,390
|1,209,989
|0.12%
|1.1
|0.35
|306.09
|style="text-align:left" |chr_LRUH 0 chr_H 0 MitM_CTL NG maxT 100000 NG_n 4 run
|-
|style="text-align:left" |Terry Ligocki
|1,209,989
|1,209,974
|0.00%
|0.9
|0.00
|381.42
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 16 H 1 tH 0 n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,209,974
|1,201,890
|0.67%
|2.5
|0.90
|134.19
|style="text-align:left" |chr_LRUH 16 chr_H 12 MitM_CTL NG maxT 10000 NG_n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,201,890
|1,200,086
|0.15%
|1.3
|0.37
|248.36
|style="text-align:left" |chr_LRUH 10 chr_H 6 MitM_CTL NG maxT 30000 NG_n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,200,086
|1,199,734
|0.03%
|1.2
|0.08
|270.32
|style="text-align:left" |chr_asth 0 chr_LRUH 3 chr_H 3 MitM_CTL NG maxT 100000 NG_n 3 run
|-
|style="text-align:left" |Terry Ligocki
|1,199,734
|1,198,893
|0.07%
|2.3
|0.10
|147.66
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 2 mod 6 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,198,893
|1,165,493
|2.79%
|4.5
|2.05
|73.44
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 30000 H 4 mod 4 n 1 run
|-
|style="text-align:left" |Terry Ligocki
|1,165,493
|1,153,863
|1.00%
|9.3
|0.35
|34.88
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 4 H 0 tH 1 n 4 run
|-
|style="text-align:left" |Terry Ligocki
|1,153,863
|1,144,711
|0.79%
|3.7
|0.69
|87.51
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 10000 H 6 mod 5 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,144,711
|1,127,789
|1.48%
|7.9
|0.60
|40.26
|style="text-align:left" |chr_LRUH 18 chr_H 8 MitM_CTL NG maxT 30000 NG_n 3 run
|-
|style="text-align:left" |Terry Ligocki
|1,127,789
|1,124,762
|0.27%
|4.7
|0.18
|66.75
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 10000 LRUH 3 H 0 tH 1 n 8 run
|-
|style="text-align:left" |Terry Ligocki
|1,124,762
|1,117,226
|0.67%
|5.6
|0.37
|55.36
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 30000 LRUH 12 H 0 tH 1 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,117,226
|1,109,057
|0.73%
|7.7
|0.30
|40.49
|style="text-align:left" |chr_LRUH 8 chr_H 4 MitM_CTL NG maxT 100000 NG_n 3 run
|-
|style="text-align:left" |Terry Ligocki
|1,109,057
|1,083,097
|2.34%
|11.4
|0.63
|27.06
|style="text-align:left" |chr_LRUH 20 chr_H 12 MitM_CTL NG maxT 30000 NG_n 5 run
|-
|style="text-align:left" |Terry Ligocki
|1,083,097
|1,077,833
|0.49%
|11.2
|0.13
|26.81
|style="text-align:left" |chr_LRUH 8 chr_H 8 MitM_CTL NG maxT 100000 NG_n 4 run
|-
|style="text-align:left" |Terry Ligocki
|1,077,833
|1,066,795
|1.02%
|24.1
|0.13
|12.40
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 2 tH 1 n 2 run
|-
|style="text-align:left" |Terry Ligocki
|1,066,795
|1,039,229
|2.58%
|52.6
|0.15
|5.64
|style="text-align:left" |chr_LRUH 14 chr_H 6 MitM_CTL NG maxT 100000 NG_n 11 run
|-
|style="text-align:left" |Terry Ligocki
|1,039,229
|1,019,286
|1.92%
|43.5
|0.13
|6.63
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 100000 H 12 mod 1 n 3 run
|-
|style="text-align:left" |Terry Ligocki
|1,019,286
|993,556
|2.52%
|66.8
|0.11
|4.24
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 8 H 2 tH 1 n 6 run
|-
|style="text-align:left" |Terry Ligocki
|993,556
|985,718
|0.79%
|78.3
|0.03
|3.53
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 1 tH 1 n 8 run
|-
|style="text-align:left" |Terry Ligocki
|985,718
|981,095
|0.47%
|83.7
|0.02
|3.27
|style="text-align:left" |MitM_CTL CPS_LRU sim 1001 maxT 100000 LRUH 6 H 1 tH 0 n 9 run
|-
|style="text-align:left" |Terry Ligocki
|981,095
|975,912
|0.53%
|79.4
|0.02
|3.43
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 100000 H 16 mod 1 n 8 run
|-
|style="text-align:left" |Terry Ligocki
|975,912
|974,180
|0.18%
|84.6
|0.01
|3.20
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 100000 H 16 mod 4 n 8 run
|-
|style="text-align:left" |Terry Ligocki
|974,180
|971,254
|0.30%
|96.9
|0.01
|2.79
|style="text-align:left" |MitM_CTL RWL_mod sim 1001 maxT 100000 H 12 mod 1 n 12 run
|-
|style="text-align:left" |Terry Ligocki
|971,254
|970,101
|0.12%
|105.6
|0.00
|2.56
|style="text-align:left" |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 8 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:
<math>*^1</math>= % Reduced,
<math>*^2</math>= Compute Time (core-hours),
<math>*^3</math>= Decided,
<math>*^4</math>= Processed)
{| class="wikitable sortable" style="text-align: right"
!rowspan="2" |Done by
!colspan="2" |Holdout TMs
!rowspan="2" |<math>*^1</math>
!rowspan="2" |<math>*^2</math>
!colspan="2" |TMs/sec/core
!rowspan="2" |Description
!rowspan="2" |Data
|-
!Input
!Output
!<math>*^3</math>
!<math>*^4</math>
|-
|style="text-align:left" |Andrew Ducharme
|970,101
|939,447
|3.16%
| --
| --
| --
|style="text-align:left" |lr_enum_continue 100_000_000 steps
| rowspan="10" |[https://drive.google.com/drive/folders/1TsSpW27x3LBlu5qmk-cjzCJzgo_3ehyT?usp=drive_link Google Drive]
|-
| style="text-align:left" |Andrew Ducharme
|939,447
|903,224
|3.86%
|440.3
|0.03
|0.59
|style="text-align:left" |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
|-
| style="text-align:left" |Andrew Ducharme
|903,224
|895,813
|0.82%
|647.7
|0.00
|0.39
|style="text-align:left" |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
|-
| style="text-align:left" |Andrew Ducharme
|895,813
|889,838
|0.67%
|609.3
|0.00
|0.41
| style="text-align:left" |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
|-
|style="text-align:left" |Andrew Ducharme
|889,838
|880,278
|1.07%
|1,638.9
|0.00
|0.15
|style="text-align:left" |Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=12 --no-ctl --lin-steps=0  --force --save-freq=1000
|-
|style="text-align:left" |Andrew Ducharme
|880,278
|877,485
|0.32%
|1,885.5
|0.00
|0.13
|style="text-align:left" |Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=6 --no-ctl --lin-steps=0  --force --save-freq=1000
|-
|style="text-align:left" |Andrew Ducharme
|877,485
|875,062
|0.28%
|2,068.8
|0.00
|0.12
|style="text-align:left" |Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=5 --no-ctl --lin-steps=0  --force --save-freq=1000
|-
|style="text-align:left" |Andrew Ducharme
|875,062
|873,469
|0.18%
|1,785.4
|0.00
|0.14
|style="text-align:left" |Enumerate.py --no-steps --exp-linear-rules --max_loops=1_000_000 --block-mult=7 --no-ctl --lin-steps=0  --force --save-freq=1000
|-
|style="text-align:left" |Andrew Ducharme
|873,469
|870,085
|0.39%
|9,270.0
|0.00
|0.03
|style="text-align:left" |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
|-
|style="text-align:left" |Andrew Ducharme
|870,085
|869,001
|0.12%
|4,498.3
|0.00
|0.05
|style="text-align:left" |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
|-
|Andrew Ducharme
|869,001
|867,008
|0.23%
|3997.4
|0.00
|0.06
|style="text-align:left"|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:
<math>*^1</math>= % Reduced,
<math>*^2</math>= Compute Time (core-hours),
<math>*^3</math>= Decided,
<math>*^4</math>= Processed)
{| class="wikitable sortable" style="text-align: right"
! colspan="2" |Holdout TMs
! rowspan="2" |<math>*^1</math>
! rowspan="2" |<math>*^2</math>
! colspan="2" |TMs/sec/core
! rowspan="2" |Description
! rowspan="2" |Data
|-
!Input
!Output
!<math>*^3</math>
!<math>*^4</math>
|-
|867008
|811301
|6.43%
|0.043
|364.10
|5666.72
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 1 tH 1 n 2
| rowspan="20" |[https://drive.google.com/drive/folders/18njhmOzRc67zCmVuLd0aDxl6ETBhL1gy?usp=sharing Google Drive]
|-
|811301
|806119
|0.64%
|0.159
|9.03
|1413.42
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 3 H 1 tH 1 n 2
|-
|806119
|736690
|8.61%
|0.548
|35.21
|408.78
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 1 tH 1 n 2
|-
|736690
|736504
|0.03%
|0.009
|5.81
|23021.56
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 1 H 1 tH 1 n 1
|-
|736504
|735317
|0.16%
|0.058
|5.71
|3540.88
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 2 H 0 tH 0 n 2
|-
|735317
|733717
|0.22%
|0.341
|1.30
|599.28
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 2
|-
|733717
|673920
|8.15%
|3.8
|4.43
|54.32
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 4
|-
|673920
|652828
|3.13%
|~10
| ---
| ---
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 6 H 2 tH 2 n 4
|-
|652828
|645264
|1.16%
|~12
| ---
| ---
| style="text-align:left" |FAR CPS_LRU maxT 100000 LRUH 8 H 2 tH 2 n 4
|-
|645264
|641388
|0.60%
|~15
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 100000 LRUH 10 H 2 tH 2 n 10
|-
|641388
|635505
|0.92%
|~200
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 10 H 1 tH 2 n 10
|-
|635505
|616639
|2.97%
| ---
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 2 H 0 tH 0 n [3-10]
|-
|616639
|592039
|3.99%
|~700
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 3 H 0 tH 0 n [1-10]
|-
|592039
|576938
|2.55%
|~800
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 3 H [0-1] tH [0-1] n [1-10]
|-
|576938
|572963
|0.69%
|~1000
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 4 H 0 tH 0 n [1-10]
|-
|572963
|567971
|0.87%
|~1000
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 4 H 2 tH 0 n [1-10]
|-
|567971
|566096
|0.33%
|~1000
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 6 H 0 tH 0 n [1-10]
|-
|566096
|564290
|0.32%
|~1000
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 0 tH [0,2] n [1-10]
|-
|564290
|559553
|0.84%
|~1000
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 1 n [1-10]
|-
|559553
|558039
|0.27%
|~900
| ---
| ---
|style="text-align:left"|FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 2 n [1-10]
|}
|}
==References==
 
== References ==
<!--
<!--
A far more efficient pipeline would immediately apply lr_enum_continue out to 1M steps to Terry Ligocki's holdout list. lr_enum_continue, written in C++, is about 400x faster than Enumerate.py at checking for Lin Recursion. Using Enumerate.py meant its Reverse Engineering decider was applied to all holdouts, and solved 74,089 TMs (0.33% of holdouts)...at the cost of roughly 274.1 hours of compute.
A far more efficient pipeline would immediately apply lr_enum_continue out to 1M steps to Terry Ligocki's holdout list. lr_enum_continue, written in C++, is about 400x faster than Enumerate.py at checking for Lin Recursion. Using Enumerate.py meant its Reverse Engineering decider was applied to all holdouts, and solved 74,089 TMs (0.33% of holdouts)...at the cost of roughly 274.1 hours of compute.
-->
-->


[[Category: BB Domains]]
[[Category: BB Domains]][[Category:BB(2,6)]]

Latest revision as of 19:05, 2 February 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
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 8 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 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
Andrew Ducharme 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
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
Andrew Ducharme 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
Andrew Ducharme 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
867008 811301 6.43% 0.043 364.10 5666.72 FAR CPS_LRU maxT 100000 LRUH 2 H 1 tH 1 n 2 Google Drive
811301 806119 0.64% 0.159 9.03 1413.42 FAR CPS_LRU maxT 100000 LRUH 3 H 1 tH 1 n 2
806119 736690 8.61% 0.548 35.21 408.78 FAR CPS_LRU maxT 100000 LRUH 4 H 1 tH 1 n 2
736690 736504 0.03% 0.009 5.81 23021.56 FAR CPS_LRU maxT 100000 LRUH 1 H 1 tH 1 n 1
736504 735317 0.16% 0.058 5.71 3540.88 FAR CPS_LRU maxT 100000 LRUH 2 H 0 tH 0 n 2
735317 733717 0.22% 0.341 1.30 599.28 FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 2
733717 673920 8.15% 3.8 4.43 54.32 FAR CPS_LRU maxT 100000 LRUH 4 H 2 tH 2 n 4
673920 652828 3.13% ~10 --- --- FAR CPS_LRU maxT 100000 LRUH 6 H 2 tH 2 n 4
652828 645264 1.16% ~12 --- --- FAR CPS_LRU maxT 100000 LRUH 8 H 2 tH 2 n 4
645264 641388 0.60% ~15 --- --- FAR CPS_LRU maxT 100000 LRUH 10 H 2 tH 2 n 10
641388 635505 0.92% ~200 --- --- FAR CPS_LRU maxT 1000000 LRUH 10 H 1 tH 2 n 10
635505 616639 2.97% --- --- --- FAR CPS_LRU maxT 1000000 LRUH 2 H 0 tH 0 n [3-10]
616639 592039 3.99% ~700 --- --- FAR CPS_LRU maxT 1000000 LRUH 3 H 0 tH 0 n [1-10]
592039 576938 2.55% ~800 --- --- FAR CPS_LRU maxT 1000000 LRUH 3 H [0-1] tH [0-1] n [1-10]
576938 572963 0.69% ~1000 --- --- FAR CPS_LRU maxT 1000000 LRUH 4 H 0 tH 0 n [1-10]
572963 567971 0.87% ~1000 --- --- FAR CPS_LRU maxT 1000000 LRUH 4 H 2 tH 0 n [1-10]
567971 566096 0.33% ~1000 --- --- FAR CPS_LRU maxT 1000000 LRUH 6 H 0 tH 0 n [1-10]
566096 564290 0.32% ~1000 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 0 tH [0,2] n [1-10]
564290 559553 0.84% ~1000 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 1 n [1-10]
559553 558039 0.27% ~900 --- --- FAR CPS_LRU maxT 1000000 LRUH 8 H 2 tH 2 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=6106"