Why Busy Beaver Hunters Fear the Antihydra

In the summer of 2024, I reported on an online community that nailed down the precise value of a number called BB(5) — the first big breakthrough in 50 years on an old problem in theoretical computer science known as the busy beaver game. BB(5), now known to be 47,176,870, is the fifth of the so-called busy beaver numbers, which measure the complexity of the craziest computations that simple computer programs can complete.

The next step in this idiosyncratic research effort is to identify the sixth busy beaver number BB(6), and there has been some notable progress on that front — I wrote a follow-up story about it a few months ago. But busy beaver researchers don’t expect to nail down the true value of BB(6) any time soon. That’s because doing so would require them to understand the behavior of a program with the awesome name “Antihydra,” which resembles a longstanding open problem in mathematics called the Collatz conjecture. A twitter user sharing my first busy beaver story summed up this state of affairs more succinctly:

Both of my stories alluded to the Antihydra barrier only very briefly. In this blog post I will explore it in more detail: What exactly is Antihydra, what is the Collatz conjecture, how are they connected, and what makes them so daunting?

Busy Beaver Basics

If you haven’t already read my two Quanta stories about the busy beaver game, I recommend doing so before reading further, mainly just because they’re both really fun! Here I’ll recap how the busy beaver game works so that we’re all on the same page.

I wrote above that the busy beaver numbers “measure the complexity of the craziest computations that simple computer programs can complete.” To define them more precisely, we first need a mathematical framework for gauging the complexity of computer programs themselves, to decide which ones are “simple.” Then we need a way to quantify the complexity of computations — what computer programs do — so that we can identify the craziest ones.

In the busy beaver game, computer programs are represented by hypothetical devices called Turing machines, which compute in discrete steps by reading and writing 0s and 1s on an infinite tape divided into cells. A unique list of rules governs the behavior of each Turing machine. Anything you can do with an ordinary computer program, you can in principle do with the right set of Turing machine rules. “In principle” is doing a lot of work in this sentence — even if you managed to acquire the requisite infinite tape, computing with a Turing machine would be horrendously inefficient. But Turing machines are easier to analyze theoretically than more practical programming languages.

Let’s unpack how Turing machines work in a bit more detail. At each step, a Turing machine consults one of its rules and edits one cell on the tape. Each rule has two cases: what to do if the current cell contains a 0, and what to do if it contains a 1. “What to do” here means what to write in the current cell, which direction to move next, and which rule to consult for the next step. One case of one rule breaks this pattern: It tells the Turing machine to “halt,” or stop running. But by itself, the existence of this instruction doesn’t guarantee that a Turing machine will halt — the machine might never get there. Quanta’s visual designer Kristina Armitage encapsulated all of this in a beautiful infographic.

The number of rules that a Turing machine has will be our measure of program complexity. This choice lets us replace our vague question about the craziest things that simple computer programs can do with a series of specific questions about different degrees of craziness, corresponding to different busy beaver numbers. You learn the value of BB(1) by answering the question “what’s the most complex computation that a one-rule Turing machine can complete?” Likewise, BB(2) measures the most complex computation that a two-rule machine can complete, and so on.

To answer these questions, we need a precise definition of what makes one computation more complex than another. A natural measure is how many steps the Turing machine needs to complete the computation. “Complete” is important — every Turing machine that never halts will run for infinitely many steps, but that’s not really a fair comparison. The number of steps that a Turing machine takes before halting (and indeed, whether it halts at all) can depend on the initial pattern of 0s and 1s on the tape. For the busy beaver game, we always start from the so-called “blank tape,” which has 0s in every cell.

We now have all the necessary pieces to formally define the busy beaver numbers. Let’s take BB(6) to be specific: It is the longest finite runtime among all six-rule Turing machines, when those machines start with a blank tape. Finding this number is straightforward in principle. First, list out all possible six-rule Turing machines. Next, sort them into two categories: those that will eventually halt when they start running on the blank tape, and those that will run forever. Toss out all the non-halting machines. Finally, measure how many steps each of the halting machines takes before stopping. The largest number is BB(6).

The problem with this plan lies in the second step, where you divide the Turing machines into two groups based on whether or not they halt. It turns out that deciding whether a Turing machine will halt can be an extremely hard problem, to put it mildly. And if you can’t tell whether a given machine will halt, then you don’t know whether your list of halting Turing machines is complete, so you can’t know whether you’ve found the longest runtime! As of this writing, researchers have classified the vast majority of six-rule machines as either halting or non-halting. But there are 1,618 “holdouts” whose fate remains unknown.

Antihydra is one of these holdout machines. To nail down the value of BB(6), researchers must first determine whether Antihydra halts, and that seems to be beyond the reach of any known mathematical technique. To understand why, we need to take a step back and ask, “what exactly are these Turing machines doing?”

Leveling Up

You may object at this point that we already know exactly what these Turing machines are doing: Each one is just following a specific sequence of rules, writing 0s and 1s on the tape as it goes. But this “low-level” description is a bit like saying “when I push these buttons, my pocket calculator toggles transistors on and off in this specific pattern.” That may very well be true, but “high-level” descriptions like “when I push these buttons, my pocket calculator multiplies 3 and 4” are usually more useful.

There’s no guarantee that any given Turing machine’s behavior admits such a simple high-level description. But remember that Turing machines can carry out all possible computations — that means that at least some Turing machines must be executing programs with high-level descriptions that humans can understand.

Actually, the most notable five- and six-rule Turing machines that busy beaver researchers have studied so far all have relatively simple high-level descriptions — that includes the longest-running five- and six-rule machines that eventually halt, the most complex non-halting five-rule machines, and holdouts like Antihydra.

Let’s look at a specific example. The fifth busy beaver, which runs for 47,176,870 steps before halting, obeys the following low-level rules:

In 1993, the mathematician Pascal Michel proved that these rules are equivalent to a simple high-level program:

1. Set \(x = 0\).
2. Divide \(x\) by 3 and check the remainder.
   • If the remainder is 0, calculate \((5x + 18)/3\). The result is your new value of \(x\).
   • If the remainder is 1, calculate \((5x + 22)/3\). The result is your new value of \(x\).
   • If the remainder is 2, halt.
3. If you haven’t halted, go back to step 2 and plug in the new value of \(x\).

Once you have a high-level description like this, you can use it to determine whether the machine will halt — and if so, exactly how many steps it will take. In this case, the high-level program just repeatedly plugs in new values of \(x\) until it finds one that leaves a remainder of 2 when divided by 3. One third of numbers have this property, so you might guess that the program will take three tries to find one, give or take a few. If you start from a random value of \(x\), you’ll find that three iterations is indeed typical. But it turns out that if you start from \(x = 0\), this program will repeat the second step 15 times before it lands on a number with remainder 2! Busy beaver researchers often like to anthropomorphize the Turing machines they study, imagining that the machines are actively trying to run for as long as possible. Adopting that perspective, we might say that this Turing machine got very lucky.

The fifth busy beaver is just one member of a family of “Collatz-like” Turing machines whose high-level behavior has the following general form:

1. Set \(x\) equal to some starting value (which may or may not be 0).
2. Divide \(x\) by a fixed number \(N\). The remainder tells you what formula to use to get your new value of \(x\).
3. Check if you’ve met a specific halting condition. If not, go back to step 2 with the new value of \(x\).

The family of Collatz-like Turing machines includes both halting and non-halting machines. It gets its name from a procedure for generating number sequences devised in 1937 by the mathematician Lothar Collatz:

1. Choose a starting value for \(x\).
2. Check whether \(x\) is even or odd.
   • If it’s even, calculate \(x/2\). The result is your new value of \(x\).
   • If it’s odd, calculate \(3x + 1\). The result is your new value of \(x\).
3. Check whether \(x = 1\). If not, go back to step 2.

This looks very similar to our general description of high-level behavior for Collatz-like machines, with \(x = 1\) as the halting condition. Try iterating these rules from any initial integer value of \(x\) — I’m willing to bet however much you like that you’ll eventually hit 1. The Collatz conjecture asserts that this happens for every positive integer, no matter how large. People have tested this empirically for all integers up to at least 2 billion trillion (!) without finding any counterexamples, which strongly suggests that the conjecture is true. But nobody knows how to rigorously prove it.

Cryptozoology

Let’s take a step back. At the beginning of this post I noted a link between the Collatz conjecture and Antihydra: Nobody knows how to prove the Collatz conjecture, and that’s why researchers don’t know how to conclusively determine whether Antihydra halts. But now I’ve instead linked the Collatz conjecture to the fifth busy beaver, a machine that has been proved to halt. What’s going on here?

The resolution to this apparent puzzle is that for the busy beaver game, we only care about whether a Turing machine halts when it starts running from a specific tape configuration, namely the blank tape. That means we only care about whether the corresponding Collatz-like sequence halts for a single input. The Collatz conjecture, meanwhile, asks whether you eventually hit \(x = 1\) for every input. It’s easy to show that the Collatz sequence ultimately hits \(x = 1\) for any one input, just as it’s easy to show that the fifth busy beaver halts (once you’ve established an equivalence between its low-level rules and the high-level Collatz-like program).

We can easily construct a variant of the Collatz problem that’s hard to solve even for a single input. All we need to do is change the \(3x + 1\) rule for odd numbers to \(5x + 1\). In that case, trajectories that start from certain inputs (such as \(x = 7\)) look like they will diverge, never hitting 1 or falling into a cycle. But researchers haven’t been able to prove that any of these trajectories diverges. There’s an inherent asymmetry here. If you want to prove that a sequence does eventually end up somewhere, you can always just use brute force, at least in principle. But if you want to prove that a sequence never terminates, even a single input can be hard.

We’re now finally ready to confront the terror that is Antihydra. It obeys the following high-level rules:

1. Set \(x = 8\).
2. Check whether \(x\) is even or odd.
   • If it’s even, calculate \(3x/2\). The result is your new value of \(x\). Add one to a running tally of how many times you’ve applied this even rule.
   • If it’s odd, calculate \((3x-1)/2\). The result is your new value of \(x\). Add one to a running tally of how many times you’ve applied this odd rule.
3. Check whether your “odd” count is more than twice as large as your “even” count. If so, halt. If not, go back to step 2.

This is a very curious set of rules. The formulas \(3x/2\) and \((3x-1)/2\) don’t appear to systematically favor odd or even numbers, so you might expect that iterating them again and again will look like repeatedly flipping a coin and keeping track of how often you get heads versus tails. Early on in a sequence of coin flips, it’s distinctly possible that you’ll end up with more than twice as many heads as tails. But if this doesn’t happen right away, it becomes less and less likely the longer you keep going. Researchers have now simulated the behavior of Antihydra out to more than 270 billion steps, and as expected, the “even” and “odd” tallies are pretty close to equal — nowhere near the extreme imbalance demanded by the halting condition. So it seems overwhelmingly likely that Antihydra never halts. But nobody knows how to prove it! The mathematician John Conway coined the delightful term “probviously” for situations like this — ones where the specific problem of interest is very hard to solve, but probabilistic reasoning about the “typical” behavior of similar problems makes the answer seem obvious.

Antihydra’s behavior is qualitatively similar to the \(5x + 1\) version of the Collatz conjecture, where we don’t know how to prove that any single trajectory diverges. I want to stress that as far as researchers know, there isn’t a more precise mathematical link between these two problems: If you resolved one of them, it wouldn’t automatically resolve the other. But the problems seem hard for very similar reasons. If someone does manage to prove the Collatz conjecture, the mathematical techniques used in the proof would likely be promising for the Antihydra problem (and vice versa).

Actually, Antihydra is just one of many probviously non-halting Turing machines with Collatz-like behavior. Busy beaver hunter Shawn Ligocki dubbed these machines “cryptids” when they were first identified in variants of the standard busy beaver game.

The first two cryptids to be discovered were named Bigfoot and Hydra; researchers have now identified so many cryptids that it no longer makes sense to give each one its own name. The existence of all these cryptids implies that busy beaver numbers beyond BB(5) will remain out of reach until researchers develop new mathematical tools for tackling Collatz-like problems. And the legendary mathematician Paul Erdős reportedly said “Mathematics may not be ready for such problems.”

But that doesn’t mean busy beaver hunters should give up. There’s still plenty of questions to explore in what might be called “cryptid ecology.” How many subspecies of cryptids are there? How are they related to each other, and to other unsolved problems in mathematics beyond the Collatz conjecture? Since the beginning of the busy beaver game, avid hunters have repeatedly encountered surprising new Turing machine behavior, and that pattern shows no sign of letting up.

This past August I visited Tahquamenon Falls in Michigan’s upper peninsula, a part of the state that’s apparently an epicenter of bigfoot sightings. Fortunately I didn’t encounter any cryptids, but I did learn some new things about a few friendlier critters. Surprising discoveries can come from anywhere!