The original version of this story appeared in Quanta Magazine.
Imagine that someone gives you a list of five numbers: 1, 6, 21, 107 and—wait for it—47,176,870. Can you guess what comes next?
If you’re stumped, you’re not alone. These are the first five busy beaver numbers. They form a sequence that’s intimately tied to one of the most notoriously difficult questions in theoretical computer science. Determining the values of busy beaver numbers is a daunting challenge that has attracted a cult following among both professional and amateur mathematicians for over 60 years.
Researchers identified the first four busy beaver numbers in the 1960s and 1970s. The conspicuously larger fifth number, called BB(5), was only definitively pinned down last year, by a team made up mostly of amateur mathematicians working together in an online community called the Busy Beaver Challenge.
No one knows how big BB(6) is. All we have are lower limits—truly staggering ones. In 2022 busy beaver hunters established that BB(6) must be, at a minimum, so large that it’s literally impossible to write down in ordinary decimal notation. Even if you somehow carved a digit into every atom in the cosmos, you’d run out of atoms before making any measurable progress.
“It’s way beyond anything that we could ever grasp or get our hands on,” said Scott Aaronson, a computer scientist at the University of Texas, Austin.
Busy beaver hunters have now discovered that this stupefyingly big number must be even bigger. The finding comes from one of the most mysterious and prolific contributors to the Busy Beaver Challenge, who proved a new lower limit on BB(6) in June and broke the record again a mere nine days later. The new results make the 2022 lower bound look positively puny.
“I keep on being surprised,” said William Gasarch, a computer scientist at the University of Maryland. “Six is getting us into the stratosphere of large numbers.”
Beaver Trap
The notoriously difficult question behind the busy beaver numbers is this: Given the code of a computer program, can you tell whether it will eventually stop or run forever?
In 1936, the pioneering logician Alan Turing proved that there’s no universal procedure for answering this question, which became known as the halting problem. Any method that works for some programs will fail for others, and in some cases, no method will work.
Turing proved this seminal result by inventing a formal mathematical model of computation in which programs are represented by hypothetical devices now called Turing machines. Each Turing machine performs computations in discrete steps according to a unique list of simple rules. The more rules a Turing machine has, the more complex its behavior can get, and the harder it can be to determine whether it will halt.