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:
One caveat: “encodes the Collatz conjecture” isn’t quite true, as we’ll see later.
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.
Graphic from “Busy Beaver Hunters Reach Numbers That Overwhelm Ordinary Math,” by Kristina Armitage/Quanta Magazine
... continue reading