Home Online Mathematical Communication Shtetl-Optimized BusyBeaver(5) is now known to be 47,176,870

BusyBeaver(5) is now known to be 47,176,870

Shtetl-Optimized 2024-07-02

The news these days feels apocalyptic to me—as if we’re living through, if not the last days of humanity, then surely the last days of liberal democracy on earth.

All the more reason to ignore all of that, then, and blog instead about the notorious Busy Beaver function! Because holy moly, what news have I got today. For lovers of this super-rapidly-growing sequence of integers, I’ve honored to announce the biggest Busy Beaver development that there’s been since 1983, when I slept in a crib and you booted up your computer using a 5.25-inch floppy. That was the year when Allen Brady determined that BusyBeaver(4) was equal to 107. (Tibor Radó, who invented the Busy Beaver function in the 1960s, quickly proved with his student Shen Lin that the first three values were 1, 6, and 21 respectively. The fourth value was harder.)

Only now, after an additional 41 years, do we know the fifth Busy Beaver value. Today, an international collaboration called bbchallenge is announcing that it’s determined, and even formally verified using the Coq proof system, that BB(5) is equal to 47,176,870—the value that’s been conjectured since 1990, when Heiner Marxen and Jürgen Buntrock discovered a 5-state Turing machine that runs for exactly 47,176,870 steps before halting, when started on a blank tape. The new bbchallenge achievement is to prove that all 5-state Turing machines that run for more steps than 47,176,870, actually run forever—or in other words, that 47,176,870 is the maximum finite number of steps for which any 5-state Turing machine can run. That’s what it means for BB(5) to equal 47,176,870.

For more on this story, see Ben Brubaker’s superb article in Quanta magazine, or bbchallenge’s own announcement. For more background on the Busy Beaver function, see my 2020 survey, or my 2017 big numbers lecture, or my 1999 big numbers essay, or the Googology Wiki page, or Pascal Michel’s survey.

The difficulty in pinning down BB(5) was not just that there are a lot of 5-state Turing machines (16,679,880,978,201 of them to be precise, although symmetries reduce the effective number). The real difficulty is, how do you prove that some given machine runs forever? If a Turing machine halts, you can prove that by simply running it on your laptop until halting (at least if it halts after a “mere” ~47 million steps, which is child’s-play). If, on the other hand, the machine runs forever, via some never-repeating infinite pattern rather than a simple infinite loop, then how do you prove that? You need to find a mathematical reason why it can’t halt, and there’s no systematic method for finding such reasons—that was the great discovery of Gödel and Turing nearly a century ago.

More precisely, the Busy Beaver function grows faster than any function that can be computed, and we know that because if a systematic method existed to compute arbitrary BB(n) values, then we could use that method to determine whether a given Turing machine halts (if the machine has n states, just check whether it runs for more than BB(n) steps; if it does, it must run forever). This is the famous halting problem, which Turing proved to be unsolvable by finite means. The Busy Beaver function is Turing-uncomputability made flesh, a finite function that scrapes the edge of infinity.

There’s also a more prosaic issue. Proofs that particular Turing machines run forever tend to be mind-numbingly tedious. Even supposing you’ve found such a “proof,” why should other people trust it, if they don’t want to spend days staring at the outputs of your custom-written software?

And so for decades, a few hobbyists picked away at the BB(5) problem. One, who goes by the handle “Skelet”, managed to reduce the problem to 43 holdout machines whose halting status was still undetermined. Or maybe only 25, depending who you asked? (And were we really sure about the machines outside those 43?)

The bbchallenge collaboration improved on the situation in two ways. First, it demanded that every proof of non-halting be vetted carefully. While this went beyond the original mandate, a participant named “mxdys” later upped the standard to fully machine-verifiable certificates for every non-halting machine in Coq, so that there could no longer be any serious question of correctness. (This, in turn, was done via “deciders,” programs that were crafted to recognize a specific type of parameterized behavior.) Second, the collaboration used an online forum and a Discord server to organize the effort, so that everyone knew what had been done and what remained to be done.

Despite this, it was far from obvious a priori that the collaboration would succeed. What if, for example, one of the 43 (or however many) Turing machines in the holdout set turned out to encode the Goldbach Conjecture, or one of the other great unsolved problems of number theory? Then the final determination of BB(5) would need to await the resolution of that problem. (We do know, incidentally, that there’s a 23-state Turing machine that encodes Goldbach.)

But apparently the collaboration got lucky. Coq proofs of non-halting were eventually found for all the 5-state holdout machines.

As a sad sidenote, Allen Brady, who determined the value of BB(4), apparently died just a few days before the BB(5) proof was complete. He was doubtful that BB(5) would ever be known. The reason, he wrote in 1988, was that “Nature has probably embedded among the five-state holdout machines one or more problems as illusive as the Goldbach Conjecture. Or, in other terms, there will likely be nonstopping recursive patterns which are beyond our powers of recognition.”

Maybe I should say a little at this point about what the 5-state Busy Beaver—i.e., the Marxen-Buntrock Turing machine that we now know to be the champion—actually does. Interpreted in English, the machine iterates a certain integer function g, which is defined by

  • g(x) = (5x+18)/3 if x = 0 (mod 3),
  • g(x) = (5x+22)/3 if x = 1 (mod 3),
  • g(x) = HALT if x = 2 (mod 3).

Starting from x=0, the machine computes g(0), g(g(0)), g(g(g(0))), and so forth, halting if and if it ever reaches … well, HALT. The machine runs for millions of steps because it so happens that this iteration eventually reaches HALT, but only after a while:

0 → 6 → 16 → 34 → 64 → 114 → 196 → 334 → 564 → 946 → 1584 → 2646 → 4416 → 7366 → 12284 → HALT.

(And also, at each iteration, the machine runs for a number of steps that grows like the square of the number x.)

Some readers might be reminded of the Collatz Conjecture, the famous unsolved problem about whether, if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. As Scott Alexander would say, this is not a coincidence because nothing is ever a coincidence. (Especially not in math!)

It’s a fair question whether humans will ever know the value of BB(6). Pavel Kropitz discovered, a couple years ago, that BB(6) is at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 (i.e., 10 raised to itself 15 times). Obviously Kropitz didn’t actually run a 6-state Turing machine for that number of steps until halting! Instead he understood what the machine did—and it turned out to apply an iterative process similar to the g function above, but this time involving an exponential function. And the process could be proven to halt after ~15 rounds of exponentiation.

Meanwhile Tristan Stérin, who coordinated the bbchallenge effort, tells me that a 6-state machine was recently discovered that “iterates the Collatz-like map {3x/2, (3x-1)/2} from the number 8 and halts if and only if the number of odd terms ever gets bigger than twice the number of even terms.” This shows that, in order to determine the value of BB(6), one would first need to prove or disprove the Collatz-like conjecture that that never happens.

Basically, 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).

I first learned about the BB function in 1996, when I was 15 years old, from a book called The New Turing Omnibus by A. K. Dewdney.  From what I gather, Dewdney would go on to become a nutty 9/11 truther.  But that’s irrelevant to the story.  What matters was that his book provided my first exposure to many of the key concepts of computer science, and probably played a role in my becoming a theoretical computer scientist at all.

And of all the concepts in Dewdney’s book, the one I liked the most was the Busy Beaver function. What a simple function! You could easily explain its definition to Archimedes, or Gauss, or any of the other great mathematicians of the past. And yet, by using it, you could name definite positive integers (BB(10), for example) incomprehensibly larger than any that they could name.

It was from Dewdney that I learned that the first four Busy Beaver numbers were the unthreatening-looking 1, 6, 21, and 107 … but then that the fifth value was already unknown (!!), and at any rate at least 47,176,870. I clearly remember wondering whether BB(5) would ever be known for certain, and even whether I might be the one to determine it. That was almost two-thirds of my life ago.

As things developed, I played no role whatsoever in the determination of BB(5) … except for this. Tristan Stérin tells me that reading my survey article, The Busy Beaver Frontier, was what inspired him to start and lead the bbchallenge collaboration that finally cracked the problem. It’s hard to express how gratified that makes me.

Why care about determining particular values of the Busy Beaver function? Isn’t this just a recreational programming exercise, analogous to code golf, rather than serious mathematical research?

I like to answer that question with another question: why care about humans landing on the moon, or Mars? Those otherwise somewhat arbitrary goals, you might say, serve as a hard-to-fake gauge of human progress against the vastness of the cosmos. In the same way, the quest to determine the Busy Beaver numbers is one concrete measure of human progress against the vastness of the arithmetical cosmos, a vastness that we learned from Gödel and Turing won’t succumb to any fixed procedure. The Busy Beaver numbers are just … there, Platonically, as surely as 13 was prime long before the first caveman tried to arrange 13 rocks into a nontrivial rectangle and failed. And yet we might never know the sixth of these numbers and only today learned the fifth.

Anyway, huge congratulations to the bbchallenge team on their accomplishment. At a terrifying time for the world, I’m happy that, whatever happens, at least I lived to see this.