What lurks at the edge?
kertlis/Getty Images
Amateur mathematicians are closing in on an unimaginably huge number – one so large that it brushes up on the edge of what is even knowable within the framework of modern mathematics.
It all stems from a seemingly simple question: how do you know if a computer program will run forever? Answering this starts with mathematician Alan Turing. In the 1930s, he showed that any computer algorithm can be mimicked by imagining a simple “Turing machine” that reads and writes 0s and 1s on an infinitely long tape by following a set of instructions called states, with more complex algorithms requiring more states.
For every number of states, such as 5 or 100, there are finitely many corresponding Turing machines, but it is unclear for how long each of these machines must run. The longest possible run-time for each number of states is called the Busy Beaver number or BB(n), and this sequence grows incredibly quickly: BB(1) is 1, BB(2) is 6, but the fifth Busy Beaver number is 47,176,870.
The exact value of the next Busy Beaver number, the sixth, is unknown, but an online community called the Busy Beaver Challenge is attempting to discover it – they uncovered BB(5) in 2024, putting an end to a 40-year search. Now, a member known as “mxdys” has discovered it must be at least as big as a number that is so large that even describing it requires some explanation.
“This number is so far beyond physical, it’s not even funny,” says Shawn Ligocki, a software engineer and Busy Beaver Challenge contributor. He compares the search through all the possible Turing machines to fishing in some deep mathematical sea where only odd, exotic bits of code swim in the dark.
The new bound for BB(6) is so large as to require mathematical language that transcends exponentiation – the practice of raising one number n to the power of another x, or nx, such as 2³, which is 2*2*2 = 8. First, there is tetration, sometimes written as xn, which involves iterated exponentiation, so 32 would be 2 raised to the power of 2, to the power of 2, which is equal to 16.
Remarkably, mxdys has shown that BB(6) is at least 2 tetrated to the 2 tetrated to the 2 tetrated to the 9, a tower of iterated tetration, where each tetration is, in turn, a tower of iterated exponentiation. The number of all particles in the universe looks puny in comparison, says Ligocki.
But the Busy Beaver numbers aren’t important just because of their absurd size. Turing proved that there must be some Turing machines whose behaviours cannot be predicted under ZFC theory, a foundation that undergirds all standard modern mathematics. He was inspired by mathematician Kurt Gödel’s “incompleteness theorem”, which showed that the rules of ZFC itself cannot be used to prove that the theory is guaranteed to be absolutely free of all contradictions.
“The study of Busy Beaver numbers is making the phenomena discovered by Gödel and Turing nearly a century ago quantitative and concrete,” says Scott Aaronson at the University of Texas at Austin. “Instead of merely saying that Turing machines must elude the capability of ZFC to determine their behaviour after some finite point, we can now ask, does that happen already with 6-state machines or only with 600-state machines?” Researchers have so far proven that BB(643) would elude ZFC theory, but many of the smaller numbers haven’t been explored yet.
“The Busy Beaver problem gives you a very complete scale for pondering the frontier of mathematical knowledge,” says computer scientist Tristan Stérin, who launched the Busy Beaver Challenge in 2022.
In 2020, Aaronson wrote that the Busy Beaver function “probably encodes a huge portion of all interesting mathematical truth in its first hundred values”, and BB(6) is no exception. It seems to be related to the Collatz conjecture, a famously unsolved mathematical problem that involves repeating simple arithmetic operations on numbers and seeing whether they eventually become 1. Finding BB(6) seems to be related to a Turing machine that would have to mimic some of the steps of this problem in order to halt. If such a machine were found to halt, it would indicate that there is a computational proof for a version of the conjecture.
The numbers the researchers are dealing with are incredible in their magnitude, but the Busy Beaver framework provides a metre stick for what would otherwise be a seemingly unintelligible region of mathematics. In Stérin’s view, this is what keeps so many of the contributors hooked, even though most of them aren’t academics. He estimates that there are currently a few dozen who are constantly working on finding BB(6).
There are still several thousand “holdout” Turing machines whose halting behaviour hasn’t been checked, he says. “Around the corner, there could be a machine that is unknowable,” says Ligocki, meaning that it is independent of ZFC and beyond the bounds of modern mathematics.
Could the exact value of BB(6) also be around the corner? Ligocki and Stérin both say that they know better than to try and predict Busy Beaver’s future, but recent success in bounding the number gives Ligocki an “intuition that there’s more coming”, he says.
Topics:
