Blanking Beavers: Results and Open Problems

SCENARIO: The year is 1950, and a brand new Turing machine, the first of its kind, has been installed at a research facility. Lots of people want to use it, but the machine has just one tape. A program’s execution can be affected in undesirable ways by data left over on the tape from a previous program run, and so as a matter of etiquette the convention is adopted among the machine’s users that the tape is to be wiped clean after each use. Rather than cleaning the tape manually after program execution, the programmers soon figure out how to automate the wiping process by writing their programs with cleanup routines at the end. Such programs are called self-cleaning.

Here’s a question: when started from the blank tape, what is the longest that a Turing machine program of a given length can run before reaching the blank tape again? We call this the Blanking Beaver problem, and the function that maps program length to maximum blank-to-blank runtime we call BLB.

We leave the tape blank out of consideration for others. As it was said in olden times: “Be kind, rewind.” But suppose we don’t care about the other users of the Turing machine. Instead, we just want to know the longest a program can run before halting, without any regard for the junk left over on the tape. This is the classic Busy Beaver problem (BB).

BB is a notorious example of a function that is uncomputably fast-growing. What about BLB? Here are the best known values:

At first glance it would appear that BLB grows faster than BB. Actually the story becomes a little more complicated when we consider different ways of measuring program length, but clearly BLB grows fast. And it is obvious from experience that BLB is equicomputable with BB, in the sense that an oracle for one problem could be used to solve the other.

We’ll examine those values later. But first there is a basic question about BLB. Is it possible to prove that BLB(s) < BLB(1 + s)? That is, given some BLB value, can we obtain a greater BLB value by adding one extra state? This is clearly true, but it is surprisingly difficult to prove.¹ It is easy to prove the analogous statement for BB by construction, since a halting program’s “halt instruction” offers a convenient modular hook-in point for the new state to attach. But a self-cleaning program does not need to have a halt instruction, so there is no nice modular interface. On the other hand, it is easy to prove that BLB(s) < BLB(2 + s) via a standard instruction-padding construction.

Here are the current BLB champions, the self-cleaning programs that run for the number of steps listed above. The 4x2, 2x4, and 3x3 champs were discovered by Nick Drozd (yours truly), while the 5x2 champ was discovered by Shawn Ligocki.

    +-----+-----+         +-----+-----+         +-----+-----+-----+-----+
4x2 |  0  |  1  |     5x2 |  0  |  1  |     2x4 |  0  |  1  |  2  |  3  |
+---+-----+-----+     +---+-----+-----+     +---+-----+-----+-----+-----+
| A | 1RB | 1LC |     | A | 1RB | 1LE |     | A | 1RB | 2RA | 1RA | 2RB |
+---+-----+-----+     +---+-----+-----+     +---+-----+-----+-----+-----+
| B | 1RD | 1RB |     | B | 0LC | 0LB |     | B | 2LB | 3LA | 0RB | 0RA |
+---+-----+-----+     +---+-----+-----+     +---+-----+-----+-----+-----+
| C | 0RD | 0RC |     | C | 0LD | 1LC |
+---+-----+-----+     +---+-----+-----+         +-----+-----+-----+
| D | 1LD | 1LA |     | D | 1RD | 1RA |     3x3 |  0  |  1  |  2  |
+---+-----+-----+     +---+-----+-----+     +---+-----+-----+-----+
		      | E | 0RC | 0LA |     | A | 1RB | 1RC | 2RA |
		      +---+-----+-----+     +---+-----+-----+-----+
					    | B | 0RC | 2RA | 0RB |
					    +---+-----+-----+-----+
					    | C | 2LC | 2LB | 0LA |
					    +---+-----+-----+-----+

It is worth noting that these programs all share a peculiar trait: they are all zero-reflexive, i.e. they all contain an instruction that reads a blank and stays in the same state. We will come back to this point later.

More details in past blog posts:

• Mother of Giants
• A New Record in Self-Cleaning Turing Machines
• Another New Record in Self-Cleaning Turing Machines
• A Tetrational Self-Cleaning Turing Machine

The 2x2, 3x2, and 2x3 champion programs are not hard to find, and are left as an exercise for the reader.

About the 2x5 and 6x2 categories: I have attempted a search of the 2x5 space, and the best I could find was a program that blanks the tape in around 10¹⁰⁰ steps. I don’t believe that is anywhere close to the true value of BLB(2,5), and I didn’t bother to record it. As far as I know, nobody has attempted a search for BLB(6,2). There is one known 6x2 tetrational blanker (~10↑↑16); however, it is just an extension of a former BB(6,2) champ found by Pavel Kropitz. Again, I do not believe it is anywhere close to the true value of BLB(6,2). I consider both of these to be fully open problems.

I claim the following:

• The current 4x2 and 2x4 BLB champs are in fact the true champions.
• The current 5x2 champ is likely not the true champion.
• The current 3x3 champ looks like it could be the true champion, but then again it might not be.

I have not produced a formal proof of the 4x2 and 2x4 values in Lean / Rocq / etc, but I am claiming that such a proof could be produced². Such a proof would be just like the BB(5,2) proof. All of the proof techniques developed for the halting problem – backward reasoning, CPS, FAR, etc – can be easily adapted for the blanking problem.

Take backward reasoning. To refute halting, we construct a hypothetical final halting configuration based on the program’s halt instruction. For example, 1RB0LA_0RC1RC_1RD1LA_1LB--- halts when it reaches D1. The rest of the tape contents don’t matter, so we start from this configuration:

D1 | ? [1] ?

To refute blanking, we imagine the last step the machine would take before the tape becomes blank. In such a configuration, there is just one mark on the tape, and everything else is blank. Then we need to gather all the possible erase instructions (instructions that print a blank over a mark). For example, 1RB0RC_1LB0LC_0RD0LD_1RA0LA has four erase instructions, and so refuting blanking requires refuting four possible configurations:

A1 | 0+ [1] 0+
B1 | 0+ [1] 0+
C1 | 0+ [1] 0+
D1 | 0+ [1] 0+

For BLB(5,2), the situation is much worse: there are Cryptids, programs whose behavior is known to be equivalent to a difficult math problem. The current champ runs for some 10¹⁴⁰⁰⁶ steps³ before blanking the tape. However, a slight modification (changing its E0 instruction from 0RC to 1RC) makes it run a trajectory that appears to reach blank, but only after an unknown number of steps. Determining whether this modified program reaches the blank tape is equivalent to solving the following⁴:

H : ℕ × ℕ → ℕ

H(n, 0) = n

H(n, 1) = H(1, n + 3)

H(4k + 0, m) = H(7k + 14, m - 2)
H(4k + 1, m) = H(7k +  8, m - 1)
H(4k + 2, m) = H(7k + 15, m - 1)
H(4k + 3, m) = H(7k + 14, m - 2)

H(1, 1)

This is an iterated Collatz-like function, which combines the possible non-totality of Collatz with the non-feasibility of Ackermann. See this post for more details. If you can solve it, let me know!⁵

As for BLB(3,3), the current champion value of ~10↑↑6 seems plausible to me. But I don’t have a strong opinion about it, and proving it seems out of reach. BB(3,3) already contains Cryptids.

Finally, there is BLBi, the instruction-based variation of BLB. Instead of counting program length by states and colors, we count by total instructions. I am pretty sure that BLBi(8) = BLB(2,4), but I haven’t been able to prove it fully. I have come up with three holdouts:

1RB0RA0LB_0LC0LA1RA_1LA2LC---
1RB1LA---_2LA0RC1RB_2LC2LB0RC
1RB2LA0LC_2LA---2RB_1RC0LC1RA

Possibly these are irregular.

Obviously BLBi(9) ≥ BLB(3,3). I would guess that inequality is strict (i.e. BLBi(9) > BLB(3,3)), but I really have no idea.

The machine is started with a blank tape in state A. The program is run until the tape becomes blank again. What happens after that? We are not requiring halting here, so the machine will keep going⁶. What does it do?

This depends on the state the machine is in at blank time. There are a few possibilities. If the machine is in state A, then it has returned to its initial configuration⁷, and it will proceed to do whatever it has just done again and again and again. Otherwise, the machine is in some other state. It could at that point do something totally different, effectively restarting computation as a different program with a different behavior. Or it could enter into some kind of obviously degenerate configuration, thereby signaling that the computation is terminated.

A priori it is not clear what a BLB champion should be expected to do after reaching the blank tape. The tiny BLB(2,2) champ reaches the blank tape in state A, while the BLB(2,3) champ enters into a simple four-step loop after reaching blank. In every other case the champ almost immediately enters into an obviously degenerate configuration. Recall the zero-reflexive instructions mentioned earlier. If a zero-reflexive occurs on the blank tape, then the machine will get stuck in that single instruction forever. We call this behavior spinning out, and that is what they all do.

In particular, no non-trivial known champs reach blank tape in state A. Indeed, in the searching that I’ve done, it seems that aiming to reach the blank tape in the initial state is a terrible strategy for achieving a high BLB score. I have found one long-running TM that returns to the initial configuration:

    +-----+-----+-----+-----+
    |  0  |  1  |  2  |  3  |
+---+-----+-----+-----+-----+
| A | 1RB | 0RA | --- | --- |
+---+-----+-----+-----+-----+
| B | 2RC | 2RB | 0RA | 0RB |
+---+-----+-----+-----+-----+
| C | 1LD | 1RC | --- | --- |
+---+-----+-----+-----+-----+
| D | 1LB | 3RD | 1LD | --- |
+---+-----+-----+-----+-----+

It runs for some 10 ↑↑ 3 steps before reaching the blank tape in state A. This is not a very good score for an 11-instruction program, but it does demonstrate that this sort of thing is possible.

Here are some Blanking Beaver open problems. They are grouped as theory, search, and proof.

Theory

1. Prove (preferably by construction) that BLB(s) < BLB(1+s).
2. Is it always the case that BB(s,c) < BLB(s,c)?
3. Define upper bounds for BB and BLB in terms of each other.
4. Characterize the post-blanking behavior of BLB champions, or show that this cannot be done.
5. Given a BB champion program, what is the shortest extension of that program that blanks the tape?

Search

1. Find a good value for BLB(2,5).
2. Find a good value for BLB(6,2).
3. Find a value for BLBi(9) better than BLB(3,3).

Proof

1. Formally prove BLB(4,2).
2. Formally prove BLB(2,4).
3. Formally prove BLBi(8).
4. Prove whether the BLB(5,2) Cryptid blanks the tape.
5. Develop novel proof techniques that apply specifically to BLB.

¹ An obvious idea is to add a state at the beginning that prints blank-on-blank and then transitions to the original program, thereby increasing the program’s BLB score by 1. But we are considering a strict interpretation of BLB such that the score is counted the first time the blank tape is reached.

² My claim should be understood along the lines of Allan Brady’s claim that he had proved BB(4,2).

³ That is, a number with 14007 digits. This is just small enough to print out in full if you really, really wanted to look at it.

⁴ Function clauses are matched top-to-bottom.

⁵ I’ve been throwing this problem at AI for a while now with no luck. So apparently math is not yet completely solved.

⁶ For purposes of BLB, we can ignore the “halt instruction”.

⁷ This ignores any offset from the starting position. If the tape is infinite and blank, then the position doesn’t matter.