Monkeys, typewriters, and busy beavers

Busy beavers are mind-bending yet hopelessly impractical.

If you follow geeky news, you probably came across a computer science concept known as busy beavers. That said, unless you’re a mathematician by training or trade, the articles make it hard to understand what the concept means and why you should (or shouldn’t) care.

In today’s article, I’d like to take a stab at answering these questions in a more accessible way. If you have some experience with software, it should be easy to follow along.

Quick recap: the halting problem

The halting problem is the most famous concept in theoretical computer science. Most simply, it states that there are (theoretical) algorithms whose outcomes can’t be decided by an algorithm.

The simplest (if slightly mushy) proof by contradiction is to imagine that we have a function, halts(x), that — given the specification of an arbitrary program x — returns true if the program halts or false if it doesn’t. If such an algorithmic oracle exists, we can construct the following code:

function foo() {
  if (halts(foo)) loop_forever();
}

This program doesn’t halt if and only if the oracle deems it to be a halting program. In this scenario, the existence of halts(x) creates a paradox, so it follows that a universal function of this type can’t exist.

Note that the proof doesn’t deal with computational complexity; it deals with impossibility. It also doesn’t say that your program is undecidable — just that a mean-spirited programmer could theoretically create one.

A constrained-memory computer

Fundamentally, a computing environment consists of “state” at time t, along with a fixed set of rules used to derive a new state for t + 1. Although there are several ways to slice and dice it, we could say that the state is a combination of RAM contents, CPU registers, and so on; while the rulebook for state transitions (state[t] → state[t + 1]) is the hardware architecture of the CPU.

Assuming no external interference, any deterministic real-world computer can only enter a finite number of states; for example, a toy architecture equipped with 16 bits’ worth of registers and RAM of can only occupy one of 2¹⁶ distinct states. It doesn’t matter how complex is the CPU rulebook: a “maximal” configuration could cycle through all 2¹⁶, but after that, the machine must either halt or be doomed to re-enter one of its prior configurations. In the latter case, because the system is deterministic and its entire universe is 16 bits, the computer becomes stuck in an endless loop: all the previously-visited states it can advance to eventually lead to the same juncture again.

This allows us to make an interesting observation: any computer algorithm with a state entirely contained in n bits of memory will either stop within 2ⁿ cycles or it will never terminate. In a finite-memory setup, the halting problem is fully decidable — albeit not always in a reasonable time.

Practicalities aside, that seems to give us a working implementation of halts(x) that simply emulates any given program for 2ⁿ cycles, returning true if the program terminated in that finite time window or false if it didn’t. This possibility sounds like trouble for the reason outlined before:

function foo() {
  if (halts(foo)) loop_forever();
}

Luckily, such an implementation of halts(x), running on a machine with n bits of total state, can only emulate programs that require fewer than n bits. After all, we need a bit of extra memory to actually keep track of the number of execution cycles and bail out once they exceed 2ⁿ. In other words, the self-referential paradox is averted in the presence of a memory constraint.

A constrained-instruction computer

In the preceding section, we talked about a computer with a limited amount of memory but an arbitrarily large rulebook. We can also approach it the other way round: we can envision a machine with unbounded memory but a fixed number of instructions. This setup is analogous, although it differs in an interesting way.

But first, we need to define the terms a bit more precisely: “one extra bit of internal state” was pretty clear, but “one extra instruction” is not. The particulars of the definition aren’t important as long as we’re being coherent. With this in mind, to strip the concept of computer instructions to the bone, we usually turn to a model known as the Turing machine. The machine consists of a read-write head positioned over an endless run of tape. The head features an internal “state” register — a bit of a misnomer — that can take one of n values. The tape is divided into cells; each cell stores a symbol from some finite alphabet (here, just “0” or “1”). For the purpose of this particular experiment, the cells are assumed to be all zeroes at the start.

In every cycle, the head reads the cell directly underneath. It then uses a predefined rulebook — a fixed-size lookup table — to decide what to do based on the symbol read from the tape and the value of the internal register. The lookup table specifies three things: the new symbol to write to the current cell, the new value to load into the internal register, and the direction to advance the head in (one cell to the left or to the right). Further, one of the register values is designated as “halt”.

The number of possible values of the internal register (n), together with the number of symbols in the tape alphabet, dictate the size of the rulebook — and therefore, the instruction set of the imagined CPU. In this setting, same as before, the maximum execution time is finite and varies in relation to n; if a given machine runs any longer than this limit, it’s destined to be stuck in a non-terminating loop.

This brings us to the concept of busy beaver numbers: n-th busy beaver, BB(n), is defined as the execution time of a maximally complex terminating program described by a rulebook for a two-symbol Turing machine with an n-valued internal register. Again, the particulars of this Turing machine are not important; the key insight is that there is a theoretical upper bound on execution time for terminating programs and that it scales with program size.

For very small values of n, this worst-case terminating program can be found by brute force: we simply examine all possible rulebooks, quickly reject the obvious duds and trivial endless loops, and then zero in on a comparatively small number of ambiguous cases to see if and when they terminate. That said, this approach was successful only for n ≤ 5. Past that point, the complexity explodes. Worse, in contrast to the scenario discussed in the earlier section, there’s no algorithm that can predict the value for an arbitrary n.

To understand why, recall that we’re back in the realm of unbounded memory, so the halting problem is relevant again. If we had an algorithmic way to calculate BB(n) for any program size n, this would also give us a general (if impractical) way to implement halts(x): we could simply simulate the algorithm for BB(n) cycles. If it halts, we return true; if it doesn’t halt in the allotted time, it will never terminate, so we can return false. But we have already established that for proper “infinite memory” Turing machines, such an oracle function can’t exist. Since the existence of an algorithm to find BB(n) would allow the oracle function to be constructed, the algorithm itself must not exist.

What we can establish is the lower bound; it’s essentially a competition to envision terminating programs with pathological execution complexity. Because of these thought experiments, we know that the maximum number of execution cycles explodes quite dramatically. In fact, BB(6) is known to have more digits than could fit in the physical universe.

A monkey with a typewriter

This is where it gets a bit wacky. Assuming you have unlimited memory, it’s not particularly hard to write a small program that would numerically probe an unsolved mathematical problem for all eternity, halting only if an inconsistency is found. For example, just 27 state transitions are needed for a Turing machine that keeps testing the Goldbach conjecture. The conjecture is that every even natural number greater than 2 is a sum of two primes. An easy coding task, if seemingly pointless.

But if we somehow knew the value of BB(27), we could assert that in theory — even if not in practice — the Goldbach conjecture, which deals with an infinite series of numbers, can be numerically solved by checking a finite number of steps. If our program doesn’t stop in BB(27) steps, it necessarily continues forever, so we have the verdict after at most this many cycles.

That's… a bit mind-blowing, I suppose. But I’m tempted to counter with a less glamorous thought experiment: let’s imagine a monkey with a typewriter. The monkey is taught to write every possible string, starting from length 1 and moving up:

Length 1: a, b, c, … z
Length 2: aa, ab, ac, … ba, bb, bc, … zz
Length 3: aaa, aab, aac, … aba, abb, abc, … zzz

And so on. If the monkey keeps typing, and if the Goldbach conjecture is provably true, we know for sure that the monkey will produce a proof in finite time. Conversely, if the conjecture is false or unprovable, the monkey will keep typing forever without giving us a solution that checks out.

Is that equally mind-blowing? If not, why?

Well, but hold on!

One natural objection is that the busy beaver approach is giving us something more up front: a specific number of cycles needed to declare success, akin to being able to tell in advance that the monkey-produced Goldbach proof is going to be exactly 6,783 words long.

Except, not really? BB(27) is not a number we can reason about: it appears to be essentially unknowable. It’s akin to saying that the monkey proof will be “potato purple” words long. It’s a label, but at least at this point, the label doesn’t mean anything.

The odds of finding that meaning seem slim, too. Another issue is that a program of some fairly modest complexity (m) can be used to iteratively test an entire system of mathematical axioms — for example, the ZFC set theory that underpins most of modern math. If the tested system is consistent, the program will run forever; if it isn’t, it must stop after finding an issue in at most BB(m) steps.

Again, we can’t compute BB(m), but it’s enough for the number to be theoretically knowable within the axiom system. If it is, we can argue that the system has an exhaustive, internal proof of consistency that can be executed in a finite number of steps.

Alas, this cannot be! Another proof closely related to the halting problem — Gödel’s incompleteness theorem — tells us that for any sufficiently expressive set of axioms, such a self-consistency proof is impossible. From Gödel’s proof, it follows that we’re not merely prevented from computing the value of BB(m); we’re not even allowed to have a method of verifying its correctness if the number comes to us in a dream. The gods of mathematical abstraction are pretty mean!

I suspect the most tangible result we might be getting out of busy beavers is a hierarchy of computability for open problems in mathematics: if the Goldbach conjecture needs just 27 states, while the Riemann hypothesis needs 744, this tells us… well, something new. That said, it’s not clear to me to which extent this hierarchy is a fundamental reflection on computability, and to which it’s just an artifact of the clunkiness of the Turing machine. Adding numbers with it is easier than calculating a sine. Should it be that way?…

👉 For a more rigorous discussion of busy beavers, check out the paper by Scott Aaronson. For more algorithms and math trivia, head over here.