BB(7): Difference between revisions
m (→Current Progress: Fill in some details of exploration) |
m (Corrected 97xxxx and 96xxxx due to duplication of TMs in those two ranges.) |
||
| Line 21: | Line 21: | ||
|- | |- | ||
|{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}} | |{{TM|1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA}} | ||
|10 ↑↑ 188 | |10 ↑↑ 188 | ||
|- | |- | ||
| Line 193: | Line 192: | ||
|Yes | |Yes | ||
|No | |No | ||
| | |1036863 | ||
|{{TM|TBD}} | |{{TM|TBD}} | ||
|TBD | |TBD | ||
| Line 200: | Line 199: | ||
|@tjligocki | |@tjligocki | ||
|Yes | |Yes | ||
| | |No | ||
| | |1436051 | ||
|{{TM| | |{{TM|TBD}} | ||
| | |TBD | ||
|- | |- | ||
|98xxxx | |98xxxx | ||
Revision as of 20:21, 17 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 | |
|---|---|---|---|---|---|---|
| enumeration | linear rule | |||||
| 00xxxx | @Iijil | Yes | Yes | TBE | TBE (bbch)
|
TBE |
| 01xxxx | @Iijil | Yes | No | TBE | TBD (bbch)
|
TBD |
| 02xxxx | @Iijil | Yes | No | TBE | TBD (bbch)
|
TBD |
| 03xxxx | @Iijil | Yes | No | TBE | TBD (bbch)
|
TBD |
| 04xxxx | @Iijil | Yes | No | TBE | TBD (bbch)
|
TBD |
| 138xxx | Shawn Ligocki | Yes | Yes | 129930 | 1RB1RA_1RC0LC_0LD1LG_1LF0LE_1RZ1LF_0LA1LD_1RA1LC (bbch)
|
10 ↑↑ 35 |
| 139xxx | Shawn Ligocki | Yes | No | 155407 | TBD (bbch)
|
TBD |
| 43xxxx | Andrew Ducharme | No | No | TBD | 1RB0RF_1RC0LF_0LC1RD_1LE1LG_0RB1LA_1RE1LD_1RZ0LF (bbch)
|
10 ↑↑ 24 |
| 500k-500250 | @prurq | Yes | No | TBD | TBD (bbch)
|
TBD |
| 700000-701999 | @hipparcos | Yes | Yes | 160792 | 1RB0LF_1LC1LE_1RE0LD_0LC0LA_1LB1RA_0LG0RC_1RZ0LA (bbch)
|
10 ↑↑ 26 |
| 90xxxx | @tjligocki | Yes | No | 1025733 | TBD (bbch)
|
TBD |
| 91xxxx | @tjligocki | Yes | No | 1437031 | TBD (bbch)
|
TBD |
| 92xxxx | @tjligocki | Yes | No | 1037736 | TBD (bbch)
|
TBD |
| 93xxxx | @tjligocki | Yes | No | 1436093 | TBD (bbch)
|
TBD |
| 94xxxx | @tjligocki | Yes | No | 1040565 | TBD (bbch)
|
TBD |
| 95xxxx | @tjligocki | Yes | No | 1434203 | TBD (bbch)
|
TBD |
| 96xxxx | @tjligocki | Yes | No | 1036863 | TBD (bbch)
|
TBD |
| 97xxxx | @tjligocki | Yes | No | 1436051 | TBD (bbch)
|
TBD |
| 98xxxx | @tjligocki | Yes | Yes | 797084 | 1RB0LC_1LC1LD_1LA1LB_0LG1RE_1LD0RF_0RA1RE_1RZ1LA (bbch)
|
10 ↑↑ 188 |
| 99xxxx | @tjligocki | Yes | Yes | 1105427 | 1RB1RF_0RC1RG_1LD1LE_0LE1LD_0RF0LC_1RA0LC_0RF1RZ (bbch)
|
10 ↑↑ 286 |