How long can a Turing machine program run when started on the blank tape before the tape becomes blank again? Of course, this will depend on the length of the program – how many states and colors it has. Even given these parameters, it is logically impossible to calculate how long a self-cleaning Turing machine can run. Any values that can be known have to be discovered empirically.

And I discovered a good one. Consider the following 2-state 4-color program:

1RB 2RA 1RA 2RB  2LB 3LA 0RB 0RA

When started on the blank tape, this program runs for 1,367,361,263,049 steps before wiping the tape clean. That’s 1.3 trillion, which seems like a lot for program that can be described with just 32 bits.

The question of how long a self-cleaning Turing machine can run is known as the Blanking Beaver problem, and it is closely related to the more well-known Busy Beaver problem.

The classic Busy Beaver problem, first posed in 1962, asks for the longest that an n-state k-color TM program can run when started on the blank tape before executing a halt instruction. Here are the best known values for short programs:

Notice that BB(4, 2) is the last “reasonable” value; after that the values “lift off”, and BB(2, 4) and BB(5, 2) are significantly greater. (Actually, the reasonable values have all been proved, but the lift-off values have not. The 5-2 champion program was discovered in 1989 (by Marxen and Buntrock) and the 2-4 champion program was discovered in 2005 (by Ligocki and Ligocki). It’s been a while, to be sure, and nobody (incuding me) has been able to find a program that does any better, but they still haven’t been proved.)

In July 2021 I discovered a 4-state 2-color program that reaches the blank tape in 32,779,477 steps. At that point, the table of values looked like this (where BB is Busy Beaver and BLB is Blanking Beaver):

There’s a huge gap between BB(4, 2) and BB(5, 2), but BLB(4, 2) just about closes the gap; BB(5, 2) is not even half again as much. This led me to the working hypothesis that BLB(2, 4) should be much greater than BB(2, 4).

And so I sat down at my workstation to search for a new champion.

A word about Turing machine simulators. I found the BLB(4, 2) champion program using a simulator written in C. It has a pretty clever design, and it’s blazing fast. But still, it is a naive simulator: the simulator executes one step for every step in the program under simulation. What’s more, it uses static tape allocation: for as many steps as the simulator will be run, that many tape cells are laid out in both directions. This obviates the need for any bounds checking, but it also means that in practice the simulator is limited to run for no more than about 268 million steps.

So after generating a list of 2-state 4-color programs using Brady’s algorithm, I ran them for 268 million steps.