Current Status
This page documents the current status of my quest for 2LBB Busy Beavers.
Overview
The table below lists the search results for square grids for which a complete exhaustive search has been carried out. The meaning of the columns is as follows:
- Size
- The size of the program grid
- #Programs
- The total number of programs evaluated by the search
- #Hangs Detected
- The number of hangs that were automatically recognized
- #Hangs Assumed
- The number of hangs that were not automatically recognized by the current search program. These programs are assumed to be hanging because their execution exceeded a pre-configured cut-off run length
- Max Run Length
- The number of steps that the Busy Beaver (Champion) required
- Cut-off Run Length
- When the execution of program exceeds this amount of steps, it is assumed to hang. It is Not Applicable when all hanging programs are automatically detected.
- Search Time
- The time required by the search. This time varies and also depends on the machine. The reported times are for a single-threaded search on my 2.5 GHz Mac Mini.
| Size | #Programs | #Hangs Detected | #Hangs Assumed | Max Run Length | Cut-off Run Length | Search Time |
|---|---|---|---|---|---|---|
| 3×3 | 31 | 0 | 0 | 5 | N/A | 7 ms |
| 4×4 | 518 | 25 | 0 | 15 | N/A | 40 ms |
| 5×5 | 30547 | 4228 | 0 | 44 | N/A | 250 ms |
| 6×6 | 8,022,654 | 1,546,935 | 4 | 573 | 1M | 6.6 s |
| 7×7 | 11,004,753,615 | 2,501,543,153 | 1,392,267 | 918,785,141 | 1B | 936 h |
Hang behaviours
Table 2 shows how many programs exhibit a certain hang behavior for the various grid sizes. It distinguishes the following hang types:
- No data: A No Data Hang
- No exit: Static analysis shows that no exit can be reached from the current program state
- Periodic: A Periodic Hang stuck in a plain loop.
- Nested periodic: A Periodic Hang stuck in a nested loop.
- Regular sweep: A Sweep Hang where the sweep exhibits constant or periodic growth.
- Glider: A Glider Hang.
- A-periodic sweep: A Sweep Hang where the sweep exhibits a-periodic growth.
- Assumed: The program is assumed to hang. It does not exhibit behavior that can be detected automatically (yet).
| Hang behavior | 3x3 | 4x4 | 5x5 | 6x6 | 7x7 |
|---|---|---|---|---|---|
| No data | 0 - | 8 32.00% | 711 16.82% | 146177 9.45% | 160634156 6.42% |
| No exit | 0 - | 0 0.00% | 909 21.50% | 356882 23.07% | 548603412 21.92% |
| Periodic | 0 - | 17 68.00% | 2608 61.68% | 1036018 66.97% | 1733823981 69.27% |
| Nested periodic | 0 - | 0 0.00% | 0 0.00% | 4443 0.29% | 40347769 1.61% |
| Regular sweep | 0 - | 0 0.00% | 0 0.00% | 2453 0.16% | 13512920 0.54% |
| Glider | 0 - | 0 0.00% | 0 0.00% | 856 0.06% | 4147077 0.17% |
| A-periodic sweep | 0 - | 0 0.00% | 0 0.00% | 106 0.01% | 473838 0.02% |
| Assumed | 0 - | 0 0.00% | 0 0.00% | 4 0.00% | 1392267 0.06% |
7×7 search
The 7×7 grid is the first that features long-running terminating programs. Therefore, the search is split in three stages.
In the first stage, the run-length cut-off is one million steps. Hang detection is enabled for the first 100,000 steps. Increasing this limit lets the search detect more hangs, but slows down execution of programs that cannot (yet) be proven to hang. This stage ran for ten hours. It found 1,392,111 programs that were assumed to hang (and terminated after one million steps).
The second stages executes all programs that were assumed to hang as quickly as possible, with a run-length cut-off of one billion steps. This stage ran for 925 hours (more than 38 days). It found 97 programs that terminated, and 307 late escapes.
The third stage continues the search for each of the late escapes. It also has a cut-off of 1 billion steps but hang detection is enabled. This found 1208 programs that terminated, detected 371 hangs, and assumed that 256 programs hang.
The longest-running program that was found this way takes more than 918 million steps to execute. It's interesting to see how this compares to other terminating programs. Figure 1 shows a histogram for run lengths for terminating 7×7 programs. Both axis use a logarithmic scale. The X axis shows the maximum run length for each bin. The minimum run length is one more than the maximum of the preceding bin. The height of each bar represents the number of programs in this bin.
Given this distribution, one would not be surprised when there are programs that finish after more than 1 billion steps. It would therefore be interesting to search with a maximum run length of 10 billion steps. However, without further improvements to the search, this search would take more than a year.
Champions
6×6 Busy Beaver
For 6×6 not all hangs are automatically detected yet. There are still four hold-outs; programs for which the search program does not yet detect that it is hanging. These, however, do not terminate without 100 million steps. Furthermore, informal analysis shows that these indeed hang. So the current Champion, with run length 573, is considered the 6×6 Busy Beaver. This program is shown in Figure 2.
7×7 Busy Beaver Champion
For the 7×7 grid an exhaustive search has been completed with a cut-off limit of one billion steps. This found a program that runs for 918,785,141 steps. It is the current 7×7 Busy Beaver Champion runs and is shown in Figure 4.
Figure 3 shows the old 7×7 Busy Beaver Champion, which requires 97,601,163 steps to complete. It was found by an earlier search, with a cut-off limit of 100 million steps.
13×13 Busy Beaver Champion
For the 13×13 grid automated search is not feasible for multiple reasons. First, there are too many possible programs. Second, their run length can be much, much longer. Third, their behavior can be much more complex. It is therefore impossible to automatically analyze all possible programs. However, it is possible to manually craft long running programs and analyze them with computer support. This way a Busy Beaver Champion has been created that runs for 2.882 × 1023409 steps. See the Discussion page for more details.