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.

Table 1. The results for the completed Busy Beaver searches
Size #Programs #Hangs Detected #Hangs Assumed Max Run Length Cut-off Run Length Search Time
3×3 31 0 0 5 N/A 0.2 ms
4×4 518 25 0 15 N/A 0.4 ms
5×5 30547 4228 0 44 N/A 15 ms
6×6 8022654 1546891 48 573 1000000 3.3 s
7×7 11004753421 2496580340 6247027 9607923 10000000 60 h

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 ten million steps. This search discovered a program that required 9607923 steps to complete. However, longer-running programs have been found. Figure 1 shows the current 7×7 Champion, which executes for more than 33 million steps.

Figure 1. The current 7×7 Champion (33207907 steps)