BB(7): Difference between revisions
(Add a few corrections and new results.) |
m (added my progress to the "current progress" table) |
||
| Line 127: | Line 127: | ||
|<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> | |<math>2 \uparrow^{11} 2 \uparrow^{11} 3</math> | ||
|[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post] | |[https://discord.com/channels/960643023006490684/1369339127652159509/1373660959960469545 Discord post] | ||
|- | |||
|25xxxx | |||
|@stokastic | |||
|No | |||
|No | |||
|TBD | |||
|TBD | |||
|TBD | |||
|[https://drive.google.com/drive/folders/16_qIdWWD-wolj6zURB5ZSbY-otI4zoUF?usp=sharing Google Drive folder] | |||
|- | |- | ||
|43xxxx | |43xxxx | ||
Revision as of 06:13, 19 May 2025
The 7-state, 2-symbol Busy Beaver problem BB(7) is a mostly unexplored domain with only preliminary information.
The current BB(7) champion is 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch) discovered by Pavel Kropitz in 2025 proving the lower bound:
History
Before 2025, the only known BB(7) champions were produced by hand, not by search. Example, Milton Green designed a machine in 1964 that had sigma score 22,961 and Wythagoras modified a BB(6) champion in 2014 to produce a machine that had sigma score .
In May 2025, mxdys shared C++ code that breaks up the BB(7) enumeration into 1 million subtasks which each run for about 2 minutes and leave ~100 holdouts each. Various folks on Discord have been investigating different sections of this domain to search for champions.
Top Halters
Based on limited search through a subset of the 1 million subtasks from mxdys's code some of the top known halting machines are:
| TM | Approximate sigma score |
|---|---|
1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch)
|
|
1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ (bbch)
|
10 ↑↑ 286 |
1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA (bbch)
|
10 ↑↑ 188 |
1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ (bbch)
|
10 ↑↑ 113 |
1RB0RF_1LC0LD_1RC0LB_1LE1RG_1RA1RE_1RD0RD_0RA1RZ (bbch)
|
10 ↑↑ 93 |
1RB0RF_1LC0LD_1RC0LB_1LE1RG_1RA1RE_1RD0RD_0RA1RZ (bbch)
|
10 ↑↑ 93 |
1RB1RF_1LC1LB_0RE0LD_0LC0LB_0RA1RE_1RG1RZ_0LG0RA (bbch)
|
10 ↑↑ 63 |
1RB0RG_0RC0RF_1LD0RA_0LE0LA_1RA0LC_0LG1LC_1RE1RZ (bbch)
|
10 ↑↑ 51 |
1RB1RZ_1RC0RG_0RD1RB_0LE0RB_0LF0RA_1LB1RF_1RE1LD (bbch)
|
10 ↑↑ 50 |
1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC (bbch)
|
10 ↑↑ 35 |
Current Progress
This is a summary of the 1 million subtasks from mxdys's code that have been processed, including further processing by Shawn Ligocki's linear rule code ("TBD" = "To Be Determined", "TBE" = "To Be Entered"):
| Task range | Done by | Completed | # holdouts | Maximum Score TM | ~Sigma | Source | |
|---|---|---|---|---|---|---|---|
| enumeration | linear rule | ||||||
| 00xxxx | @Iijil | Yes | Yes | 728495 | 1RB0RF_1RC1LF_0RD0RD_1LE0LB_1RA1RZ_1LG1RA_1LD0RC (bbch)
|
10 ↑↑ 46 | Google Drive folder |
| 01xxxx | @Iijil | Yes | No | 1056253 | TBD (bbch)
|
TBD | |
| 02xxxx | @Iijil | Yes | No | 963486 | TBD (bbch)
|
TBD | |
| 03xxxx | @Iijil | Yes | No | 1052504 | TBD (bbch)
|
TBD | |
| 04xxxx | @Iijil | Yes | No | 955711 | TBD (bbch)
|
TBD | |
| 138xxx | Shawn Ligocki | Yes | Yes | 129930 | 1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC (bbch)
|
10 ↑↑ 35 | TBE |
| 139xxx | Shawn Ligocki | Yes | No | 155407 | TBD (bbch)
|
TBD | |
| 243308 | @uni | Yes | No | TBE | 1RB0RA_1LC1LF_1RD0LB_1RA1LE_1RZ0LC_1RG1LD_0RG0RF (bbch)
|
Discord post | |
| 25xxxx | @stokastic | No | No | TBD | TBD | TBD | Google Drive folder |
| 43xxxx | Andrew Ducharme | No | No | TBD | 1RB0RF_1RC0LF_0LC1RD_1LE1LG_0RB1LA_1RE1LD_1RZ0LF (bbch)
|
10 ↑↑ 24 | TBE |
| 500xxx | @prurq | Yes | No | TBD | TBD (bbch)
|
TBD | Google Drive folder |
| 700000-701999 | @hipparcos | Yes | Yes | 160792 | 1RB0LF_1LC1LE_1RE0LD_0LC0LA_1LB1RA_0LG0RC_1RZ0LA (bbch)
|
10 ↑↑ 26 | Posted to Discord |
| 90xxxx | Terry Ligocki | Yes | No | 1025733 | TBD (bbch)
|
TBD | Google Drive folder |
| 91xxxx | Terry Ligocki | Yes | No | 1437031 | TBD (bbch)
|
TBD | |
| 92xxxx | Terry Ligocki | Yes | No | 1037736 | TBD (bbch)
|
TBD | |
| 93xxxx | Terry Ligocki | Yes | No | 1436093 | TBD (bbch)
|
TBD | |
| 94xxxx | Terry Ligocki | Yes | No | 1040565 | TBD (bbch)
|
TBD | |
| 95xxxx | Terry Ligocki | Yes | No | 1434203 | TBD (bbch)
|
TBD | |
| 96xxxx | Terry Ligocki | Yes | No | 1036863 | TBD (bbch)
|
TBD | |
| 97xxxx | Terry Ligocki | Yes | Yes | 1436051 | 1RB0RG_1LC0LE_1LD0LB_1RB1RE_0RA1RF_0RD1RC_1RD1RZ (bbch)
|
10 ↑↑ 113 | |
| 98xxxx | Terry Ligocki | Yes | Yes | 797084 | 1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA (bbch)
|
10 ↑↑ 188 | |
| 99xxxx | Terry Ligocki | Yes | Yes | 1105427 | 1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ (bbch)
|
10 ↑↑ 286 | |