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.

6×6 Busy Beaver Champion

For 6×6 not all hangs are automatically detected yet. This could theoretically mean that one of the programs that is assumed to be hanging might actually terminate. However, all these programs run for more than 100 million steps. Given that this is five orders of magnitude longer than the run length of the current Champion, 573, it is unlikely that any of these programs terminate. Nevertheless, until the hang detection automatically detects all hangs, the Champion is not yet the Busy Beaver.

7×7 Busy Beaver Champion

For the 7×7 grid an exhaustive search has been completed with a cut-off limit of one hundred million steps. Hang detection was only enabled for the first 100000 steps. Increasing this limit lets the search detect more hangs, but slows down execution of programs that cannot (yet) be proven to hang. This search discovered a program that required 97601163 steps to complete. It is shown in Figure 1 and is currently the longest running 7×7 program that has been discovered. However, as its run length is close to the cut-off limit, it is likely that longer running programs exist. It is similarly likely that not all possible programs have been visited by the search; There may be late escapes beyond the cut-off limit.

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 × 10²³⁴⁰⁹ steps. See the Discussion page for more details.