The other day I found a cool new 3-state 3-color Turing machine program. Here it is:

  ０ １ ２
Ａ １ＲＢ ０ＬＢ ２ＬＡ
Ｂ １ＬＡ ０ＲＣ ０ＬＢ
Ｃ ２ＲＣ ２ＲＢ ０ＬＣ

When started on the blank tape, this program runs for more than 10 ↑↑ 6 steps before terminating.

Now, you may notice that this program has no halt instruction and therefore obviously can never halt. And given that it can never halt, you may wonder what I mean when I say that it “terminates”.

Observe that the program contains the instruction C0 -> 2RC. That is, if the machine is in state C and scanning a blank cell (0), then it will remain in state C and move right. We are starting the program from the blank tape, so there are only ever finitely many marks on the tape. So if the program should ever reach state C with the tape head to the right of all the marks, then it is clear that it will get stuck in instruction C0 forever. And indeed, this is exactly what happens – it ends up in this configuration:

C0 | 2^Q 0 [0]

That is, there is a 2-block of length Q, followed by a blank cell, and the machine is scanning another blank cell and is in state C. It is obvious that no meaningful computation can occur after this point, so we may as well just end the run there. This circumstance is known as spinning out.

Spinning out is the simplest possible behavior that a non-halting program can exhibit.

Spinning out is also an instance of a more general behavior known as quasihalting. Whereas halting means that all states become unreachable, quasihalting means that some states become unreachable. In the specific case of spinning out, all states but one become unreachable. (Indeed, all instructions but one become unreachable).

The classic Busy Beaver question (BB) asks: what is the longest that a Turing machine program of N states and K colors, when started on the blank tape, can run before halting? The program here cannot halt and so is obviously not a candidate for BB. However, the Beeping Busy Beaver question (BBB) is just the same as BB, except that it asks for quasihalting instead of halting. This is program does quasihalt, and in fact it is the new BBB(3, 3) champion! And it is now known that BBB(3, 3) > 10 ↑↑ 6.

How can such a simple program generate such a huge number? Actually, although the number is too huge to be written out in full, it is simple to specify. I said earlier that the final tape configuration reached contained a block of length Q. Here is the precise definition of Q:

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

This is a big number, but ultimately it is just a power of 2. The program achieves this by implementing a simple additive rule, then using that additive rule to implement a multiplicative rule, then applying that multiplicative rule repeatedly. This is exactly what one might expect based on the repetitive structure of Q. Calculating these rules is not terribly complex, but it does require some real math.

A few notes:

  • Running a program for tetrationally many steps cannot be done directly. It requires a fast-forwarding, algebra-aware inductive prover simulator. But for such a simulator, this program runs extremely quickly: termination is reached in only a few hundred steps.

  • The Spaghetti Code Conjecture says that Busy Beaver programs ought to be complicated, ill-structured, or otherwise “spaghetti code”. This program, however, has a fairly clean structure. It has three states, but two of those states do not communicate with each other: state A only reaches itself and state B, and likewise state C only reaches itself and state B. State B therefore acts as some sort of dispatch node, and this fact can be gleaned simply by looking at the program text. So this program is weak evidence that maybe the Spaghetti Code Conjecture is false.

  • The previous BBB(3, 3) champion was found by Shawn Ligocki back in February 2022. That program quasihalts after around 1062 steps, so it is “just” exponential, rather than tetrational like this new one. When announcing that discovery, he said “I don’t think I’ll find any more without some more clever searching.” But I didn’t come up with any particularly novel search strategy – it was just standard Brady’s algorithm. So why didn’t Shawn find this one? I think it was simply a matter of being in the right place at the wrong time. He was the first person to find a tetrational program, but that didn’t happen until May 2022, a few months after his BBB(3, 3) search. After that he overhauled his simulator to handle tetrational numbers, but I suppose he didn’t go back to the 3-3 space after that. If he had, he probably would have found it. (My own simulator is partially based on Shawn’s. I would say it is approximately 1/3 directly similar, 1/3 distinct, and 1/3 convergently similar.)

Finally, here are the latest results for BB / BBB.

States Colors BB BBB
3 2 21 55
2 3 38 59
4 2 107 ≥ 32,779,478
2 4 3,932,964 > 1024
5 2 47,176,870 > 1014006
3 3 > 1018 > 10 ↑↑ 6
2 5 > 10 ↑↑ 4 …
6 2 > 10 ↑↑ 15 …

Proven values are stated exactly; the rest are lower bounds. Some values are provably difficult to prove. In the case 2-state 5-color and 6-state 2-color, there is no BBB result better than the best known BB result.

🚨 OPEN PROBLEM ALERT 🚨

  • Find values of BBB(6, 2) or BBB(2, 5) better than their BB counterparts.