Gaze not into the abyss of arithmetical statements, or it will gaze back.

Turing Machines are fascinating little devices for encoding mathematical problems. It asks the question of if a turing machine with a set of instructions ever reaches a specific instruction (the halt state). The way this is worded will be important later.

It turns out you can encode any "there exists" problem into the halting problem of a turing machine! But of course, that's not all the problems that exist. For example, you cannot encode the twin prime conjecture (directly at least, to my knowledge) into a turing machine. That's a "for all x, there exists a y" problem which is too much for our machines to handle.

That's where Scott Aaronson's Beeping Turing Machines come in. We can move one level up and ask if a specific state is reached infinitely often. Or, for all times that state is reached, there exists a following step for which that state is reached again. The machine "quasihalts" if the state is only reached finitely many times.

You can encode a lot more problems using this construction, but eventually you again run into a wall. How would you encode the problem, "for all collatz maps defined by k (map an integer n to \((2k + 1)n + 1\) if n is odd, \(\frac{n}{2}\) if it's even), there exists an integer such that repeatedly applying this rule goes to infinity"?

A new construction was created by Bram Cohen, named the Beeping Booping Turing Machine. Every time you reach a boop state, count how many times a beep state was reached previously and output that number. The machine "pseudoquasihalts" if there exists a number that is output infinitely often.

And that's where the ladder was stuck. While you can encode probably most interesting problems with only those 2 extra rungs, you can't encode every problem. One may ask, is there a way to generalize these two constructions?

That's what I hope to answer today.

The Problem of Oracles

Each of the previous two rungs are equivalent to equipping a turing machine with an oracle that can solve the halting problem of the rung below. To solve a machine's beeping halting problem, you need to solve its regular halting problem. And similar for the beeping booping halting problem and the beeping halting problem.

While the notion of generalized oracle turing machines is well established, the constructions of them leave a lot to be desired. There are a lot of strange, unnatural (in my opinion) choices you have to make in regards to how a turing machine communicates with its oracle, and the exact nature of the oracle itself. This is really unfortunate too, when considering other models of computation can have very straightforward and intuitive ways to extend them.

The reason the beeping, and beeping booping extensions are nice is that they have a few key properties. For one, each builds off the last, introducing only a single new "sound" per halting problem level and a rule for interpreting said sound.

For another, and in my opinion the most important part, it does not actually change the execution of the base turing machine. The transition table is enough to describe the behavior of a turing machine on the tape for all time (I.E. If you look at the tape of a turing machine at step n, it will always look the same no matter what sounds are attached). It only changes the question you're asking about it.

A generalized method of constructing halting problems of arbitrary difficulty should retain these two properties.

The Order N Halting Problem

Let an order-n "sound" correspond to a unique output upon reaching a specific instruction (or set of instructions).

Let two order-n sounds be "equivalent" if for each sound, between it and the previous order-n sound (or the start of execution), the same sequence of order-(n-1) sounds occurs (with each order-(n-1) sound also depending on the sequence of order-(n-2) sounds below it, and so on). Note that all order-1 sounds are equivalent.

With those definitions out of the way, let the following be my new definition of the order-n halting problem:

And for those of you that want a more rigorous, mathematically precise definition:

And now, I offer a proof that any statement on the arithmetical hierarchy can be encoded as a sufficiently strong halting problem with the above construction.

Theorem: Any \(\Sigma_{n + 1}\) statement can be encoded into the halting problem of an order-n turing machine.

You may have some questions about this construction. Allow me to explain.

"Why do you break the mapping from number of sounds to number of arithmetical hierarchy jumps?"

This is actually a property that was maintained in the original three constructions! You probably just didn't think about it that way.

The order-0 and order-1 halting problems only have the beep state. Though you may not think about the original halting problem having the beep state, it's halting problem is to halt the first time it beeps! It's only when you reach order-3 that you have to add a new sound. This fits with the construction.

"Is it possible to have a construction in terms of numbers like the beeping booping case instead of leaving it defined as an arbitrary equivalence class?"

Sure, here's such a construction. Although I am not prescribing this as the best way to encode the problem. As long as the unique equivalence class behavior is maintained, any construction will work.

"Why the distinction between the odd and even case?"

Because the arithmetical hierarchy makes that distinction. A \(\Pi_1\) statement corresponds to "\(\forall\)", \(\Pi_2\) corresponds to "\(\forall \exists\)", \(\Pi_3\) corresponds to "\(\forall \exists \forall\)" and so on. The value last quantifier depends on the parity of the n in \(\Pi_n\). I think it's perfectly natural to think that higher order halting problems should make the distinction.

"Can a state transition have multiple sounds attached to it?"

I think there's a strong case for allowing the overloading of states! However, to make things cleaner I won't be considering overloaded states in this article.

If you allow the overloading of states, you'd need to specify the order in which the sounds are played. Perhaps in increasing order of the sound's order.

One thing to note is that any behavior you could get with an overloaded state is also possible to achieve without overloading by adding sufficient instructions.

Both systems are sufficiently powerful to do anything interesting that the other can do. I'm curious what people think is better. Let me know!

"So why should we use this construction and not some other construction?"

Let's look back at our criterion

- It extends the Beeping and Beeping Booping constructions in a natural way. The first one especially is considered by many to almost be a "canonical" way to extend the strength of turing machines. The alternative construction by Racheline also extends the Beeping construction, but requires you to redefine the Beeping Booping construction. Mine allows you to keep that.

- Adding a higher order sound does not affect the execution of the turing machine on a lower order. This can be interpreted as any machine's tape history will remain identical no matter what sounds you add, but this is even more general. Any machine with a set of order-n sounds will not have its order-n halting problem be affected by adding a new order-(n+1) without overriding other sounds.
In my opinion, this is a very nice property.

- There is a nice correspondence between number of sounds and arithmetical strength. You need exactly \(\lfloor n/2 \rfloor\) sounds to encode any statement of \(n\) strength.

- Each jump in strength is trivial. You add one sound on the odd cases and a question associated with that sound. You don't even need to define the notion of an oracle to describe a machine's order-n halting problem.

- The extension to all higher order busy beavers is well defined.

So, while there are other constructions you can use, this construction has nice properties that many others wont. As mentioned earlier, Racheline's alternative construction also satisfies most of these, but I will discuss that later.

"Can you give an example of a construction of a machine with a higher order (>2) halting problem?"

Here's a trivial example that we can use to examine what higher order halting problems look like. Take the machine with the following transition table:

This really simple machine just counts up in binary on the tape forever. It obviously doesn't halt as it doesn't have a halt state. The order-1 halting problem would be do you always encounter a 1 on the tape moving right, which translates to "does there always exist a binary number with a 1 in the expansion"? To which the answer should obviously be yes, so this machine doesn't order-1 halt.

The order-2 halting problem asks if there is some string of consecutive 1s for which there are infinitely many binary numbers that contain that string of 1s. The answer to this is also yes, so this machine order-2 halts at step 1.

The order-3 halting problem asks if there are infinitely many starting strings of consecutive 1s that appear infinitely often. Again, because this is binary, the answer is yes so this machine does not order-3 halt.

The order-4 halting problem is equivalent to the order-3 halting problem in this case because a boop only ever occurs once between two buzzes. It's asking, when incrementing in binary, is there a sequence of ones and zeros that will always be encountered, which is true, so this machine order-4 halts at step 2.

Wait... what?

A machine order-n halting DOES NOT imply that it order-(n+1) halts!

You may be asking something along the lines of "Katelyn, what the hell have you done?" or "did you do something wrong?". Worry not! I can explain!

This was a really surprising result to me at first. However, as it turns out, this was already a property of the standard halting problem and the beeping halting problem, you probably just never thought about it like that.

You'll often see the halting problem phrased in terms of "undefined transitions". In essence, it is asking if a given state is ever reached. So for a machine to not quasihalt, it needs to reach a state infinitely many times. Thus, if you define the halting problem on a state that a machine that doesn't quasihalt on, it necessarily has to halt, otherwise that transition would never be reached in the first place and it trivially quasihalts for that state.

So in fact, the order of implication for odd n is that if a machine is order-n nonhalting, then it order-(n-1) halts. And the contrapositive is that if it does not order-(n-1) halt, it order-(n) halts.

Quick note in case it's necessary, this doesn't let you solve the halting problem. A machine order-(n-1) halting for odd n does not let you determine if it order-n halts or not.

Higher Order Busy Beavers and Notation

We can define higher order busy beaver functions now, using these higher order halting problems.

Let \(\text{BB}_k(n)\) denote the greatest number of steps made by an n-state turing machine with k unique sounds before order-k halting. I suspect very few values of these are truly solvable beyond the initial busy beaver domain. You may have more luck with \(\text{BBi}_k(n)\), where in this case n denotes the number of instructions.

Properties of Higher Order Busy Beavers

Theorem 1: Each \(\text{BB}_{k + 1}(n)\) grows uncomputably faster than \(\text{BB}_{k}(n)\) for all k. This is true because if you had a function that acted as a combination of \(\text{BB}_k(n)\) and any computable function, you could bound \(\text{BB}_{k+1}(n)\) and solve the order-(k+1) halting problem with only an order-k halting oracle, which is impossible.

Theorem 2: For even n, determining whether a machine has order-(n+1) halted is as hard as solving the order-n halting problem. For odd n, determining whether a machine has order-(n+1) halted is as hard as solving the order-n halting problem.

Remark: I cannot find a way to prove \(\text{BB}_{k+1}(n) \geq \text{BB}_{k}(n)\) for all k and n. I conjecture this may be because it's actually false in general, and there may be some obscure case where this fails. If you do have a proof (even if it's just for the even or odd case) please send it my way! However, I can prove the following:

Theorem 3: \(\text{BB}_k(n) \leq \text{BB}_{k+2}(n)\) for all k and n. This is necessarily true, because one can shift up the order of all the sounds by 2 and not include either of the 2 lowest order sounds. This gives an identical halting problem. My definitions don't stipulate that a higher order machine needs all of the lower order sounds, you'll just get a more boring machine.

Extended Standard TM Notation

If we want any hope of solving higher order busy beavers, ideally we'd have a way of compactly representing a machine with oracles attached.

Fortunately, I propose a relatively simple addition to the standard notation used for representing a TM code. We can add a single number at each state representing the order of the sound it makes.

Say we had a machine with the following transition table:

Then we could represent it with the following TM code, where each state is represented with 4 characters now:

(Note: This is just the Space Needle transition table with random sounds added. This exact configuration likely doesn't do anything interesting)

This feels like a relatively natural way to extend the existing notation without running into weird conflicts. However, the write symbol of one state and the sound order of the previous can seem to merge which is only saved by the fact that each state is 4 characters wide. If we go beyond 9 symbols, or 9 oracle levels, this notation will run into some trouble.

This is why I propose this alternative notation in which you index sound levels with a, b, c, ... (lowercase) with a being the default empty sound.

I personally lean more towards the lowercase letter notation to prevent future confusion, but I would love to hear what people think on this.

Known values of \(\text{BB}_k(n)\)

As mentioned earlier, very few values of higher order busy beavers are known! While these problems get incredibly hard very quickly, I would hope that \(\text{BB}_1(4), \text{BB}_2(3), \text{BB}_3(2), \text{BB}_4(2)\) can all be solved.

The current value for \(\text{BB}_2(2)\) comes from 1RB01LA0_0LA11RA2 / 1RBa1LAa_0LAb1RAc as proven by discord user racheline

The current bound for \(\text{BB}_3(2)\) comes from 1RBb0LBd_1LAc1RAa

I think the possibility that you encounter cryptids by \(\text{BB}_2(4)\) or \(\text{BB}_3(3)\) is real.

Extending this to solve multi-symbol machines would also be a worthwhile endeavor! As far as I know, research into higher order multi-symbol machines is basically nonexistent as of this moment.

The Single-Beep Construction

As I was fleshing out this definition, discord user Racheline introduced to me an alternative way of defining higher order halting problems that requires no additional sounds be added to a turing machine beyond the original beep state, while retaining many of the desirable properties we're after. I'll call this the single-beep construction and my construction the multi-beep construction.

It works by defining an "n-beep" to be n consecutive beeps in a row. Then for each higher level, you can look at sequences of (n-1)-beeps between n-beeps. This has all the same properties as the multi-beep construction, because an n-beep is functionally identical to a higher order beep in the multi-beep construction.

This construction has some advantages, mainly it's in some sense mathematically "simpler". You don't need to define any higher order sounds at all and a machine's higher-order behavior isn't limited by the number of instructions a machine has. As well, for a given set of instructions, the search space for the single-beep construction is smaller meaning it's easier to prove more values of the corresponding higher order busy beavers.

I personally, however, prefer the multi-beep construction and that is what I will most likely be using. My justification is that the multi-beep construction contains the definition of the beeping booping construction, so that doesn't have to be thrown out. As well, it makes the execution for a TM cleaner, and I believe you're likely to find more interesting behavior early on with the multi-beep construction even if both constructions have the same power in the limit.

The single-beep construction is also more restrictive in that you have to beep consecutively some number of times. You could create a different construction that avoids this, but then you get into the problem that whether a given beep is an n-beep becomes undecidable which is in my opinion an undesirable property.

However, this is a very cool construction! I find it fascinating only a single beep is enough to go all the way to arbitrarily complex arithmetical statements, and this specific construction is probably worth investigating on its own.

A Quick Note for the Googologists

Using the multi-beep construction, we've defined all \(\text{BB}_k(n)\) for all natural k and n. But now, some may get the temptation to start climbing highter.

Define the diagonalized \(\text{BB}_{\omega}(n) = \text{BB}_n(n)\). This is a monstrously fast growing function, that has to eventually outgrow all uncomputably faster growing \(\text{BB}_k(n)\) functions with only finite k.

Some of you may be thinking about the fast growing hierarchy seeing that, and it does feel very similar! However, I haven't found a way to generalize this notion to higher and higher ordinals while keeping in spirit with what the \(k\) represents. I'm leaving that as an exercise to the reader :)

Scott Aaronson noted in his blog post Who Can Name the Bigger Number? the following:

In keeping with this statement, I'll now define a number \(D = \text{BB}_{\omega}(10^{100})\). This is a very big number. A big dam number, if you will! It is however certainly smaller than the likes of Rayo's number

Special Thanks

Wanted to write here to say thank you to Racheline for helping me more rigorously define my construction, as well as defining the single-beep construction. I also want to thank John Tromp for his extensive and helpful feedback on the earlier draft of this article.