Most people probably don’t think of mathematics when they hear “busy beavers.” But these eager little animals symbolize one of the most amazing concepts of the knotty field: not everything can be calculated, no matter how hard you try (or how busy of a beaver you are). The busy beaver function is the first example of a noncalculable mathematical expression. The function itself is easy to explain: it refers to the largest number of steps a computer program can take before stopping if the program has n states, where states refer to the complexity of the problem. But its values, called BB(n), will never be known for all quantities of n. Mathematicians and theoretical computer scientists have long pondered at which n mathematical tools fail: Where exactly is the limit of what can be calculated?
For more than 40 years, many experts assumed that BB(5) could lie beyond this limit of computability and would therefore be unattainable. But now an international collaborative project called the Busy Beaver Challenge has succeeded in determining the value of BB(5), and its calculation was formally verified by a computer-aided proof assistant. According to the new research, the magic number for BB(5) is 47,176,870, meaning that a program with five states can take a maximum of 47,176,870 steps before halting—or it will never halt at all. The last big “busy beaver” achievement occurred in 1983, when the late computer scientist Allen Brady proved that BB(4) equals 107.
Busy beavers are deeply rooted in the foundations of mathematics. In the 20th century, many experts dreamed of finding a foundation on which all mathematical truths could be proven. But in 1931 logician Kurt Gödel, aged just 25 at the time, dashed their hopes. He proved that there are inevitably unprovable statements in mathematics—statements that can neither be proven nor disproven. Initially experts hoped this was an abstract result with no significant applications. But they were wrong.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
Mathematicians now know of many unprovable problems. One of the first examples is the halting problem, which deals with the execution of algorithms. In the 1930s Alan Turing figured out that there is no algorithm that can predict whether a computer program with certain inputs will run forever or will stop at some point. At the time, Turing was working on the theoretical model of such a computer, now called the Turing machine. This theoretical machine consists of an infinitely long tape labeled with 1’s and 0’s and a head that reads the tape, describes it and shifts it to the right or left. Such a machine can theoretically perform any kind of calculation—just like a computer.
Suppose you want to program a Turing machine to multiply two numbers. The 1’s and 0’s on the tape then correspond to the two numbers. Before the calculation, you define a certain number of states, or rules, for the machine, such as A, B, C and D, as well as HALT. These states determine how the Turing machine acts with each input. For example: If the five-state machine reads a 1 on the tape in state A, it overwrites this with a 0, moves the tape to the left and switches to state C. Two instructions are therefore required for each of the states A to D, depending on whether the machine finds a 1 or a 0 on the tape. Under certain circumstances (for example, state B when reading a 1), the machine can switch to the HALT state. In this case, the Turing machine stops, and the calculation is complete. The result would then be the numbers on the tape at that point.
As Turing proved, there is no Turing machine that can determine, for all possible configurations of Turing machines, meaning all algorithms, whether they will stop at some point. And this is where the industrious beavers come into play.
The Halting Problem
In the “busy beaver game,” developed in 1962, Hungarian mathematician Tibor Radó searched for the most diligent Turing machine of a certain size: What is the maximum number of calculation steps that a Turing machine with n states, which comes to a halt at some point, can perform?
To answer this question in general, you would have to solve the halting problem. To find the busiest beaver, you need to know which Turing machines halt (and therefore stop running at a certain step) and which do not. But Turing showed that knowing this is impossible, which means that the busy beaver function BB(n) cannot be calculated for all possible numbers of states.
Nevertheless, Radó determined the first three values of the BB function, albeit with great effort in some cases. The difficulty arises partly because of the fact that the number of possible Turing machines (computer algorithms) increases rapidly as the number of states (n) increases. For each of the two input values, 0 or 1, the Turing machine performs three different steps in a particular state:
It replaces the input with an output (0 or 1). This step has two possible operations.
It moves the tape to the right or left. This also entails two possible operations.
It changes to one of the n states or to the halt state. This step requires n + 1 possible operations.
So there are 2 x 2 x (n + 1) possible operations for each input value and each of the n states. Combining both inputs would result in a total of (4n + 4)2n different possible sets of particular steps, where each set of steps represents a different algorithm, or a different Turing machine. If only one state is allowed, there are already 64 different Turing machines. Of these, only those that switch to the HALT state after the first calculation step will stop. Because there is only one other rule in addition to HALT, if the machine doesn’t stop, it will continue carrying out that one rule forever. Therefore, none of the halting Turing machines will go beyond one calculation step, which is why BB(1) = 1.
Things get a little more complicated if you allow two states. In this case, there are already (4 x 2 + 4) raised to the fourth power, or 20,736, Turing machines that need to be examined. There is no generally valid method for investigating which Turing machines hold. As Radó found out, the longest-running program with two states—the busiest beaver—can perform six arithmetic steps, so BB(2) = 6.
Radó and his then doctoral student Shen Lin were also able to clarify the case of three states in 1965: Among the 16,777,216 Turing machines, those that halt at some point can perform at most BB(3) = 21 calculation steps. In 1963 Radó described the attempt to calculate BB(4) as hopeless. But 20 years later Brady succeeded in determining BB(4): the highest number of calculation steps for a Turing machine with four states (or four rules) is 107. This remained the last value of the busy beaver function that could be determined exactly for four decades.
'Busy Beaver' Hunters
Shortly after Brady’s result was released, the mathematics community turned to calculating BB(5) exactly. Experts organized a competition in the German city of Dortmund in 1984 in which they tried to find the fifth value of the function. The participants were looking for five-state Turing machines that perform as many calculation steps as possible before coming to a halt. The winner of the competition was computer scientist Uwe Schult, who found a program with 134,467 calculation steps. Five years later computer scientists Heiner Marxen and Jürgen Buntrock found one of the five-state machines that didn’t halt until it reached 47,176,870 steps, thus presenting a new minimum value for BB(5). It could not be proven that an even more industrious program was not lurking among the five-state Turing machines, however.
Busy beaver hunters needed to prove that all the other machines ran indefinitely or stopped sooner than the 47,176,870th step. And there are a lot of five-state Turing machines. To determine BB(n), one must clearly show that some of the Turing machines never stop. For example, you must prove that a program ends in a loop that repeats itself over and over again. It is even trickier to prove that a Turing machine continues to run indefinitely without a repeating pattern—like the decimal places of an irrational number.
The search for a halting five-state Turing machine that performs more than 47,176,870 computational steps remained unsuccessful for several decades. Therefore, many experts suspected that BB(5) = 47,176,870. But without a sound proof, this was just hypothetical.
For this reason, Tristan Stérin, then a computer science Ph.D. student, launched the Busy Beaver Challenge in 2022. The aim of the project was to collect and check all the results relating to busy beavers. For example, if someone proved that a five-state program could run indefinitely, they could publish the proof there and have it checked by a computer-assisted proof software. This allowed many interested parties to work together and present valid results. The project was completed this month, with the final proof that BB(5) is indeed 47,176,870.
Because each of the busy beavers correspond to an algorithm, you might wonder what BB(5) is actually calculating. The program corresponds to a recursive function similar to the one from the Collatz conjecture, one of the biggest unsolved problems in number theory. BB(5) calculates the value (5x + 18) / 3 for an input x if x is divisible by 3; (5x + 22) ⁄ 3 if x divided by 3 results in a remainder of 1; and if x divided by 3 has a remainder of 2, the program stops.
And the search for busy beavers continues. The record holder for Turing machines with six states already performs so many arithmetic steps that you need a new arithmetic operation to record the number in a compact way (10↑↑15, or 10 to the power of 10 to the power of 10, 15 times in total). Further, there is increasing evidence that BB(6) is probably not calculable. Most tellingly, in 2024 a six-state Turing machine was found that almost corresponds to the Collatz problem. So if one wanted to show that this machine stops (or continues to run forever), this would be tantamount to solving the Collatz problem. The Collatz conjecture states that if you start with a positive integer and follow two specific rules, you will end in a specific loop. Mathematicians have been trying to solve this problem for decades without success. One fear is therefore that the Collatz problem is one of the unprovable statements of mathematics.
In this case, attempts to calculate BB(6) would inevitably be doomed to failure. Computer scientist Scott Aaronson is also not very hopeful, as he wrote in a blog post: “If and when artificial superintelligences take over the world, they can worry about the value of BB(6). And then God can worry about the value of BB(7).” Perhaps mathematicians really have reached the limit of the calculable with BB(5). But who knows: maybe someone will manage to surprise the experts again.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.