Beeping Booping Busy Beavers
Going up the noncomputability hierarchy in an elegant way
Busy Beaver numbers are the classic example of a well defined noncomputable function. The question is: For a given number of states of a Turing Machine, what’s the maximum number of ones which can be in its final output when it halts? If we’re playing the ‘name the biggest number’ game, this can be used to easily beat everything people normally come up with.
Beeping Busy Beaver numbers grow yet even more profoundly faster than Busy Beaver numbers. For them instead of having one of the state transitions be a halt make one of the state transitions emit a ‘beep’. For a given machine the number is the number of steps it goes through before it emits its final beep. The rate of growth of these numbers is comparable to the rate of growth of machines which are given access to an oracle which can determine whether a given Turing Machine halts, but obviously the beeping construction is much more elegant. (Other things specify a particular state rather than state transation as emitting the beep. Since the transition number is always at least as large and possibly much larger I think it’s a better thing to go with.)
Now you may wonder: Can we go larger? Is there an elegant construction which corresponds in power to having a Turing Machine which can access an oracle which tells it whether a given Turing Machine which has access to whether a regular Turing Machine halts in turn halts? Sorry for how hard it is to parse that sentence, we’re looking for the level above Beeping Busy Beavers. It turns out the answer is yes there is, by having a Beeping Booping Busy Beaver, which is the new idea I’m presenting here.
Like a Beeping Busy Beaver, a Beeping Booping Busy Beaver never halts. It has two state transitions which are special, one which emits a ‘beep’ and one which emits a ‘boop’. Its output is interpreted by counting the number of beeps between each successive boop, resulting in a series of integers. To calculate its number, find the first output value which is later repeated an infinite number of times and count the number of steps it took to first finish that output.
Proving that this is computationally equivalent is left as an exercise to the reader, mostly because I don’t know how to do it, but Scott Aaronson assures me that it does in fact work. As a mathematician I’m a lot better and constructing things than proving things.
A few things jump out here. First of all the Beeping Booping construction gives some insights into which number theory questions correspond to which level of Turing Machine, which I for one didn’t realize before, so that’s an actually useful output of this silliness. Also it seems obvious that there should be some kind of Beep Boop Buzz construction which goes one higher, but oddly I have no idea how to construct that, so maybe mathematicians only rarely ask questions of that level.
Despite it not being obvious how to add in a Buzz there is a clear pattern going on here. Each Beeping Busy Beaver is a Turing Machine which was disqualified from having a Busy Beaver number because it never halts. Likewise each Beep Boop Beaver was disqualified from having a beeping number because it never stops beeping. Maybe a Beep Boop Buzz Beaver is a failed Beep Boop Beaver because each of its boop counts doesn’t repeat infinitely, but it isn’t at all obvious how that should work.
The funny thing about these higher level machines is that they aren’t new machines at all, they’re simply new ways of interpreting the behavior of regular Turing Machines. When something simply looks ‘messy’ you haven’t fully grokked the meaning of its output, and maybe there’s something very coherent which it’s doing if you think about it in the right way.