If you follow geeky news, you might have 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 this in an accessible way — and in the process, dive into some of the mind-bending limits of algorithmic knowledge. And yes: Kurt Gödel will be making an appearance. If you have some experience with software, it should be easy to follow along, and I think it’ll be worth your time.
Quick recap: the halting problem
The halting problem is the most famous concept in theoretical computer science. Most simply, it states that in an idealized computing environment, there are algorithms whose outcomes can’t be decided by another algorithm. This is usually reduced to the question of whether a program ever terminates. That said, halting is not special: we could be as well asking whether it can reach some other non-trivial state.
The basic proof by contradiction is to imagine that we have a function called halts(x). Its implementation doesn’t concern us; let’s say we found it in an ancient book of forbidden lore. The function, 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 is akin to asking a fortune-teller if you’re going to tip them and then doing the opposite. This program doesn’t halt if and only if the oracle deems it to be a halting program, so the existence of halts(x) creates a paradox. We must conclude that, just like our tip-predicting clairvoyant, an infallible halting oracle can’t exist.
Note that the proof doesn’t deal with computational complexity; it deals with logical 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 instruction set of the CPU.
Think about how a six-digit odometer in a car can only display 106 numbers, from 000,000 to 999,999. In the same vein, any deterministic computer with limited memory (and no user input) can only enter a limited number of states. For a toy computing architecture equipped with 16 bits’ worth of registers and RAM, there are 216 distinct runtime possibilities. A “maximal” execution environment can cycle through all 216 options, but after that, the machine must either halt or re-enter one of its prior configurations. In the latter case, the odometer rolls over, if you will. The system can’t see or act on anything outside its universe of 16 bits; it has no memory of having been there before. It’s destined to follow prior footsteps, stuck in an endless loop.
This allows for an interesting observation: any computer algorithm with a state entirely contained in n bits of memory will either stop within 2n execution cycles or it will never terminate. In a limited-memory setup, the halting problem is conceptually decidable — albeit not always in a reasonable time.
Practicalities aside, that seems to give us a plausible implementation of halts(x): we just need to emulate any given program for 2n cycles, returning true if the emulator terminated in that finite time window or false if it didn’t. The possibility sounds like a way to revive the earlier paradox:
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 some extra memory to actually keep track of the number of execution cycles and bail out once they exceed 2n. In other words, recursive emulation of foo() is not possible and the contradiction is neatly averted… for now.
A constrained-instruction-set computer
In the preceding section, we talked about a computer with a limited amount of memory but an arbitrarily large rulebook for state transitions. We can also approach it the other way round: we can envision a machine with unbounded memory but a limited CPU instruction set.
Before we proceed, we ought to define the terms a bit more precisely: “one extra bit of internal state” was pretty clear, but “one extra instruction” is not. The complexity of CPU instructions that are invented in an ad hoc way can vary a great deal, so we need to rein in our creativity to make the problem tractable.
The usual method is to turn to what’s known as the Turing machine. The specifics aren’t important, but briefly: the machine consists of a read-write head positioned over a potentially endless run of tape. The machine has a single internal register that can take one of m values. The tape itself 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 this model, instructions are entries in the rulebook that specify what to do based on the contents of the internal register together with the symbol read from tape. For each entry, the rulebook specifies just three things: the new value to put in the internal register, the symbol to write to the current tape location, and the direction to advance the head in (one cell to the left or to the right). Further, one of the instructions is designated as “halt”.
In our experiment, because there’s no user input and the tape starts in a blank state, each machine can only execute a single, static algorithm specified by the rulebook. The rulebook can encode arithmetic operations and conditional branching, so the model is good enough to handle any calculation we can do with a real computer (albeit very inefficiently).
Recall that in the earlier case of a machine with limited memory but an unbounded number of instructions, we could easily argue that a terminating algorithm can’t run for more than 2n cycles, where n was the amount of memory (in bits). But is there a similar limit for a machine designed with unbounded memory but a limited instruction set?
Well, it would seem so. Again, in a Turing machine, actions are selected based on the current tape symbol and the value of an internal register; both of these have a finite alphabet — 2 and m, respectively — so the effective number of instructions is capped. Further, each instruction can only choose from a limited repertoire of actions: storing one of the available symbols or moving the read-write head one cell to the left or to the right. As a consequence, for a given m , there’s a maximum number of distinct Turing machines we can create, each representing a single algorithm. The number of the available algorithms is not worth deriving or memorizing, but if you’re curious, it’s (4m+4)2m.
Now, some of the constructed algorithms will loop forever and some will terminate — but because the overall m-cohort has a finite size, there ought to be a specific terminating algorithm that runs the longest of the bunch. We call this winning entry the m-th “busy beaver” and denote the execution time as BB(m). Any algorithm in the same size class that runs longer than BB(m) is a non-terminating endless loop.
For several of the most trivial values of m, the worst-case terminating program can be found by brute force: we simply need to enumerate all possible CPU configurations, quickly reject the ones that obviously halt or loop forever, and then zero in on a comparatively small number of ambiguous cases to prove if they terminate. That said, this approach is successful only for m ≤ 5; past that point, the complexity gets out of hand. Worse, in contrast to the simple 2n rule for limited-memory scenarios, there can be no algorithm to find BB(m) for an arbitrary m.
This claim might sound suspect, but it can be thought of as a straightforward consequence of the halting problem. If we had an algorithmic way to compute BB(m) for any m, this would give us a general — if impractical — way to implement halts(x): we could choose m sufficient to represent the program x and then emulate the code for BB(m) cycles. If it halts, we return true; if it doesn’t halt in the allotted time, it must belong to the subset of programs in the size class m that do not terminate, so we can return false. But we know that the existence of halts(x) creates a paradox, and in this instance, the issue isn’t resolved by the presence of a memory limit. We must conclude that a general method of calculating BB(m) must be out of reach of a computer algorithm.
This observation, in itself, doesn’t stop us from reasoning about busy beaver numbers to some extent. For example, we can always establish the lower bound; we can organize a contest where people try to one-up each other with terminating programs that can be reasoned to run longer than the previous winning entry. Because of such competitions, we know that as m increases, the maximum number of execution cycles explodes quite dramatically. In fact, BB(6) is known to have far more digits than could fit in the physical universe.
But again, let’s not concern ourselves with practicality. Fundamentally, if BB(m) is a number, does its existence have any interesting implications for life, the universe, and everything?
A monkey with a typewriter
It does, in a way! Assuming that memory is no object, 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. In particular, we know that a Turing machine with m = 25 register values is enough to implement an algorithm that iteratively tests the Goldbach conjecture. The conjecture is that every even natural number greater than 2 is a sum of two primes.
The program sequentially checks every even positive integer to confirm this property. Common sense dictates that this approach can’t prove the Goldbach conjecture in finite time: there are infinitely many numbers to examine! But here’s where it gets wacky: if we somehow knew the value of BB(25), we could argue that the verifier program only needs to be executed for that many cycles. After all, if it doesn’t stop in at most BB(25) steps, it necessarily belongs to the subset of m = 25 programs that never terminate. And if we can show that the checker never halts, the Goldbach conjecture must be true. At that point, we can unplug the Turing machine and take a victory lap.
That’s… a bit mind-blowing. It’s as if our concept of infinity is broken in some way.
At the same time, I’m tempted to counter this 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 can be sure that the monkey — despite being engaged in an endless task — will produce a verifiable proof in finite time.
Is that equally mind-blowing? If not, why?
Well, but hold on…
One natural objection to the monkey experiment is that the busy beaver approach seems to be giving us more information: a specific number of cycles we need to wait to declare success. It’s 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(25) is not a number we can reason about: it appears to be essentially unknowable. We could perhaps stumble across it by some non-algorithmic means; until then, the concept feels about as meaningful as saying that the monkey proof will be “potato purple” words long. It’s a label, but the label doesn’t mean anything beyond a tautology: “keep going as long as needed to prove the Goldbach conjecture and not a single CPU cycle more”.
That might seem like a weak objection, but the issues run deeper than temporarily not knowing what the number might be. Past a certain point, these values just get a tad too spicy for our system of mathematics. To explain the issue, imagine a Turing machine programmed to verify standard math, the most common foundation of which is the Zermelo–Fraenkel set theory (ZFC). ZFC is just a small collection of axioms about sets (e.g. “two sets are equal if and only if they contain the same elements”); it’s good enough to formalize virtually all of mathematics and it avoids some known paradoxes that plagued several of the earlier attempts.
If you want to prove that ZFC is 100% paradox-free and if you’re not in a hurry, you can just write another Turing machine algorithm can iterates through every axiom of ZFC, then applies every available rule of inference to derive a collection of mathematical truths that follow from the starting axioms. The program can then repeat the process for the resulting corpus, continuing forever and halting only if it finds a pair of statements that contradict each other. An implementation that does something analogous actually exists: the current version requires a Turing machine with 432 register values, but many folks believe that the number — let’s call it z — can be much lower than that.
As before, if ZFC is consistent, this algorithm will never halt, because among other things, it will need to examine the properties of every natural number expressed in set-theoretic terms. But if ZFC is busted, the machine must stop after finding a contradiction in at most BB(z) steps.
Yet… we can’t have an algorithm like that.
You can’t Gödel away with this!
The issue is that if the value of BB(z) is even theoretically knowable in ZFC, we can argue that an exhaustive proof of the consistency of the system can be executed “from within” the system in finite time. Again, we have no obvious way to find the value of BB(z), but that’s irrelevant. In principle, if a race of spacefaring aliens showed up and handed the number to us, and if we could prove within ZFC that we’ve been given the correct value, there’d be nothing else standing in the way.
However we obtain the number, the possibility of constructing the proof clashes with another seminal thought experiment: Gödel’s incompleteness theorem. Kurt Gödel started with a seemingly idle philosophical question; simplifying a bit, he asked if it’s possible to have a system of mathematics (“🔮”) that’s simultaneously internally consistent, expressive enough to embed the basic arithmetic of natural numbers, and syntactically complete in the sense of being able to procedurally prove or disprove every well-formed statement expressed in the standard language of logic.
This is interesting to ponder because if such a system exists, we probably want to use it in lieu of any lesser systems that may contain unprovable statements! Yet, Gödel showed that there can be no such thing. He started by outlining a scheme for encoding first-order logic statements as natural numbers in a way that preserved a numerical relationship between the statement and its constituent parts. That is to say, if number p encoded a statement along the lines of “if <a> then <b>”, then the numbers representing sub-statements <a> and <b>, along with the “if … then …” construction, would be embedded in it and unambiguously distinguishable. If you need a crude analogy, think of how we use ASCII codes to represent text. Gödel did this with primes — a product of several primes can be factorized back into the constituent values — but the encoding scheme is just a technicality.
What’s important is that the trick reduced inference to arithmetic procedures: if the number representing statement <a> was already on the pile labeled “truth”, we could put the number representing <b> on the same pile by just doing some mechanistic calculations on the aforementioned number p. Note that I use “truth” in scare quotes: Gödel’s scheme wasn’t concerned with objective truth; it dealt with demonstrability — i.e., the ability to infer one thing from another to iteratively construct some universe of “demonstrated” numbers. His goal was simply to show that a complete apparatus for formal reasoning exists within the basic natural number arithmetic capabilities of the parent system, 🔮. He relied on a minimalistic language called Peano arithmetic, noting that this was the part you really couldn’t really futz with if they wanted the resulting mathematics to have working addition, multiplication, and a full range of integers.
Gödel also showed how to mechanically construct numbers that encode the aforementioned proof (“<a>; if <a> then <b>; therefore <b>”). With this done, he pulled off his coup de grace: he presented a method to manipulate the numbers to construct an “evil” sentence — let’s call it G — that references itself and asserts that among the system’s demonstrated numbers, there’s no value representing “<something or other>; therefore G”. Or, more succinctly: G = “G has no proof”.
The precise arithmetic construction of Gödel’s sentence is not worth getting into, but the explanation above may sound confusing to some readers: if we start with a normal sentence that’s encoded as a specific number, how can we turn it into a self-reference without altering the number and thus making the reference invalid? Well, to illustrate, let’s take the following:
The string that is the result of replacing
<THIS>with a copy of its initial form
The sentence contains a “naked” placeholder string (<THIS>) and it doesn’t seem to identify anything in particular. But if we actually make the substitution it talks about, we end up with the following:
The string that is the result of replacing “The string that is the result of replacing <THIS> with a copy of its initial form” with a copy of its initial form
This sentence awkwardly but unambiguously describes itself: it says it’s a product of a specific substitution and that’s manifestly what it is. It’s the simplest self-reference, effectively saying “I am myself”. With a bit more effort, we can build sentences that make less trivial assertions about themselves — such as “I have no proof”.
So, what are the implications of a sentence that claims to be unprovable? Well, if 🔮 isn’t consistent — if it already allows you to prove contradictory statements — then anything goes. But if the system is to be consistent, it must never allow “<something or other>; therefore G” to manifest through the application of arithmetic-based logic. It doesn’t matter why would anyone design the system to let that happen; the only point is that if we put G on the “truth” pile, we end up with an instant contradiction. A sentence that says it has no proof can’t be true if it does, in fact, have a proof.
Importantly, the same goes for any manifestation of “G is false”. If we put G on the “falsehood” pile, it’s akin to saying that it’s build-in claim of unprovability is incorrect and that G does have a proof. But if G has a proof, shouldn’t it be on the pile labeled “truth”?… So, there you have it: any system of mathematics that’s consistent and reasonably expressive can’t possibly be syntactically complete because one can always construct, but not prove or disprove, some artificially-constructed sentence. Philosophers weep.
This may seem insignificant, but Gödel didn’t stop there! He noted that because any system that can determine the value of G is destined to lose consistency, then designating a system as consistent automatically entails that it can’t know which pile to put G on. This can be shown using formal logic: consistency implies unprovability.
And that gets us to Gödel’s second question: can 🔮 itself prove its own consistency? In other words, can a practically useful system of mathematics use its own axioms to establish with certainty that it contains no contradictions?
If it can, the proof of consistency necessarily establishes the unprovability of G in 🔮. But if it proves the unprovability of G, that makes the built-in claim of Gödel’s sentence demonstrably true: it says it’s unprovable and we can actually prove that property. We take G, gently put it on the “truth” pile and… boom! There goes consistency again.
There’s only one way to fix this mess: we must conclude that systems in which G can be constructed can’t possibly show their own consistency.
Back to beaver land
Gödel’s second theorem tells us that if ZFC is consistent — we like to think so! — then we can’t be allowed to build an in-system proof of that exact property.
But before we took the scenic detour through Kurt Gödel’s mind, we were discussing an algorithm that evidently could prove the system’s consistency in finite time. Our solution was predicated on just two things: we needed a specific Turing machine program (done) and we needed to know the value of a certain integer, BB(z). Again, the value can’t be found by a computer, but we figured that we could probably procure it on the intergalactic dark web. If so, we have to add a third requirement: we need to show under ZFC that we have the genuine article and not a knock-off product. For a valid in-system proof, we can’t just say “this is BB(z), trust me bro”.
This leads to the final disappointment: since the first part is done and the second is at least conceptually possible, it must be that we’re forbidden from ever completing the third step. That is to say, ZFC must have no way of verifying the correctness of the number if the value comes to us in a dream. A guaranteed enigma; the gods of mathematical abstraction clearly don’t like what we’re trying to do.
What did we learn? Well, it’s interesting that we’ve come full circle: we started with a proof that the halting problem can’t be decided. We then introduced busy beaver numbers as a way to circumvent the limitation and construct finite-time proofs; but in the end, we had to conclude that in the general case, such proofs can’t be carried out because Kurt Gödel’s ghost shows up and puts the requisite integer on a shelf we can’t reach.
The inescapable conclusion is that Gödel's incompleteness theorem and the halting problem are two sides of the same coin: they arrive at nearly the same underlying truth, even if they do so from different angles and using dissimilar terminology. If one of the proofs is easy to grasp and the other seems hard, it’s an indictment of the abstractions we use, not one’s intellect.
I suspect the most tangible result we might be getting out the busy beaver experiment is a fairly mundane hierarchy of computability for open problems in mathematics. If the best BB-style “solver” of the Goldbach conjecture needs m = 25, while the best approach to the Riemann hypothesis needs m = 744, this tells us… well, something new. That said, it’s not clear to me to which extent these scores are a fundamental reflection on computability, and to which extent they’re just an artifact of the incredible clunkiness of Turing machines.
👉 For more articles about math, visit this page. In particular, you might enjoy:
I write well-researched, original articles about geek culture, electronic circuit design, algorithms, and more. If you like the content, please subscribe.
There's an interesting question one could ask about Gödel’s incompleteness: provability aside, is G actually true or not?
Well, G appears to be just a number; it's Gödel's encoding scheme and the associated mechanics that give it an internal meaning. That said, in the world we intended to create, we'd be tempted to say that G is semantically true: it's a complicated formula that says it can't end up on Gödel's truth pile, and it never does.
At the same time, because 🔮 can never make this determination about G, the system works independently of the semantic truth of the sentence. In other words, it's compatible both with a universe of Peano arithmetic augmented with "G = true" just as it's compatible with one constructed by saying "Peano axioms + G = false". In both cases, it can't infer the value on its own.
To clarify, when we specify the design of Peano arithmetic, we give a collection of rules for some collection of underlying objects, but we don't specify what these objects are. We just intuitively assume that the axioms perfectly select for a concrete collection of objects and object relationships (a "structure") that looks like natural numbers: there's an object representing "0", a successor we call "1", and there's nothing weird going on. In this model, G indeed ought to be semantically true.
Yet, the axioms, as expressed in the language of first-order logic, are actually loose enough that they can also be satisfied by pathological, non-standard structures that, for example, include infinite sequences of "extra" numbers unmoored from the sequence of naturals. And if PA is bootstrapped over these bizarro structures, 2 + 2 is still 4, but G can be semantically false.
The precise mechanics of these non-standard models are essentially indescribable, but they exist. If we had a formal first-order logic proof that they don't, then 🔮 could follow the same reasoning to conclude that G must be always true, and then promptly implode.
In a similar way, we can't know BB(z) because it's *independent* of the mathematical theory we're using. ZFC can be bootstrapped over various structures. Some of them match our normal understanding of sets, and some contain horrors from the deep. For the most part, ZFC works the same in all cases, but the maximum runtime for halting machines of the z size class can differ, so the theory can't pin it down.
me → this article → (woosh). Or at least after the "A constrained-instruction computer" part.