This page describes the 2LBB problem. It shows Busy Beavers for small grid sizes to make the problem more concrete. Finally, it presents a hand-crafted 9x9 program and asks how it compares to the 9x9 Busy Beaver?
The problem that is considered here is very simple:
For a given grid size, what is the longest running 2LBB program that still terminates?The longest running possible program for a given grid size is called the Busy Beaver. For certain grid sizes the Busy Beaver may not (yet) be known. In that case we can identify the Busy Beaver Champion, the longest running program that is currently known. Longer running programs may exist but have not yet been found.
This problem is a variant of the Busy Beaver game introduced by Tibor Radó in 1962 in his paper "On Non-Computable Functions". Radó was looking for Busy Beavers in n-state Turing Machines. He defined a busy beaver function Σ(n) (the Busy Beaver run length for n-state Turing Machines) and proved that it is a non-computable function. This is not only a profound result but it also inspired many mathematicians and programmers to search for these Turing Machine-based Busy Beavers.
So why search for 2LBB-based Busy Beavers? There are two reasons. One, because it's fun. The other reason is that 2LBB makes it easier to disseminate the problem and associated concepts (non-computable functions, halting problems, combinatorial explosion) to a wider audience. Compared to Turing Machines, 2L programs have a more simple visual representation. Similarly, their execution can visualised in a manner that is more easily understood. Furthermore, after a short introduction to 2LBB, people can get hands-on experience with creating long-running programs using a Go board and a set of Go stones. This is how I got hooked, by the way.
For small grid sizes exhaustive search can quite quickly find the Busy Beaver. The main difficulty is determining when a program hangs. The search needs to evaluate each program to determine how many steps it executes before it terminates. The obvious way to do this is to execute the program. If the program, however, hangs this simulation never finishes. Figure 1 shows an example of a program that never terminates.
For small grid sizes this problem can be easily circumvented by assuming a program hangs when it runs for more than a pre-configured number of steps, which is chosen suitably large. Obviously, the danger is that this limit is chosen too low, preventing the search to find a program that executes for longer, yet terminates. In practise, up to 6×6 grid sizes this is not an issue, but more about Hang Detection later.
Figure 2, 3, and 4 show the Busy Beavers for 4x4, 5x5, and 6x6 grids respectively.
Finally, Figure 5 shows a hand-crafted 9×9 program. I created this program with help of a few others after the problem was introduced to me. It runs for 61922 steps.
So what does it do? It implements two nested loops. The inner-loop decreases a counter. While doing so, it increases another value by as much as it can. When the inner-loop terminates, it shifts DP so that the new value becomes the loop counter. As this new value is higher than the original counter, the inner loop runs longer each time. The program terminates after the inner-loop executed five times. This execution is limited as DP shifts towards a non-zero guard value that was set when the program started. When this guard is encountered, the program terminates.
So, how does this program compare to the 9×9 Busy Beaver? That is what I wanted to know as well. I therefore started to implement a search program to find 2LBB Busy Beavers.