Here’s a fun one. I found a 3-state 3-color Turing machine program that, when started on the blank tape, runs for more than 10 ↑↑ 6 steps before wiping the tape clean. Behold:¹

How many steps exactly does it run? Well, that is not so easy to say. What happens is that eventually it reaches this machine configuration:

B2 | ..0 [2] 2^R 0..

That is, the machine is in state B, the only marks on the tape are a solid 2-block of length 1 + R, and the machine is scanning the leftmost 2 of that block. The program has the instruction B2 -> 0RB, so it remains in state B and proceeds to erase every 2 (i.e. overwrite with 0) as it moves to the right. Once the last 2 is erased, the tape is blank. The exact length of R is:

((-27 + (23 * (3 ** ((-13 + (23 * (3 ** ((-15 + (23 * (3 ** ((-21 + (23 * (3 ** ((-13 + (23 * (3 ** 6285))) // 8)))) // 8)))) // 8)))) // 8)))) // 4)

That’s a valid Python expression, but don’t try to evaluate it. Your interpreter might crash. However, it is possible to get a sense of how large the number is by counting the nested exponentials. In fact the exponents are five levels deep, making this a tetrational expression, with a value of “around” 10 ↑↑ 6. This is enough to make it the new Blanking Beaver champion! The Blanking Beaver game is just like the classic Busy Beaver game, except that instead of running to halt, a Turing machine is run until it erases the tape. The previous BLB(3, 3) champ runs for “only” exponentially many steps (around 10⁴²⁷⁴⁵ steps).

After erasing the last 2, the machine scans a 0, still in state B. The program has B0 -> 0RC, so it leaves the cell blank, moves right, and goes to state C. The tape is still blank, and the program has C0 -> 2LC, so the machine will get stuck executing that C0 instruction forever. That is to say, right after erasing the tape, the machine quasihalts. Therefore, this program is also a candidate for the Beeping Busy Beaver game! Here again, the Beeping Busy Beaver game is just like the classic Busy Beaver game, except that instead of running to halt, a Turing machine is run until it quasihalts.

Regular readers of this blog (???) will recall that I previously reported that BBB(3, 3) > 10 ↑↑ 6. That is, the current BBB(3, 3) champ quasihalts after 10 ↑↑ 6 steps. Well, here we have a new program that quasihalts after 10 ↑↑ 6 steps. So, do we have a new champ? Is it a tie? Or what?

You may have noticed earlier that I said a value was “around” 10 ↑↑ 6, with “around” in “scare quotes”. This is because tetrational estimation is incredibly coarse. 10 ↑↑ 6 and 10 ↑↑ 7 seem like they ought to be close-ish, because 6 and 7 are close. But 10 ↑↑ 7 is exponentially greater than 10 ↑↑ 6, so not all 10 ↑↑ 6 estimates are created equal.

We saw the expression R earlier. The current BBB(3, 3) champ produces a block of marks of length Q, where Q is:

2 ** (4 + (2 ** (4 + (2 ** (4 + (2 ** (4 + (2 ** (4 + (2 ** 20))))))))))

Which of Q and R is greater? Not obvious at first glance, but again a good clue is the nestedness of the exponentials. R has exponents nested five deep, while Q is nested six deep. This at least preliminarily suggests that Q is greater. And indeed, applying Shawn Ligocki’s extended up-arrow notation leads to finer estimates:

R ≅ 10 ↑↑ 6.54
Q ≅ 10 ↑↑ 6.74

So this new program is the new BLB(3, 3) champ, but it is not the new BBB(3, 3) champ.

Exercises for the reader

Give a proper analysis of the new program.
Determine the exact quasihalt step counts of the current BBB(3, 3) champ and the new candidate.
Exhibit nice-looking LaTeX for Q and R.
Come up with a new champ for BLB(3, 3), or else prove that this is the true champ.
This post addresses the question of step counts, but it mostly discusses mark counts. Why is that?

Footnotes

¹ In plain text:

    +-----+-----+-----+
    |  0  |  1  |  2  |
+---+-----+-----+-----+
| A | 1RB | 1RC | 2RA |
+---+-----+-----+-----+
| B | 0RC | 2RA | 0RB |
+---+-----+-----+-----+
| C | 2LC | 2LB | 0LA |
+---+-----+-----+-----+

Exercises for the reader

Related

Footnotes