The Enigmatic World of Busy Beaver Numbers

The original version of this story was featured in Quanta Magazine.

The Puzzling Sequence

Imagine being presented with a list of five numbers: 1, 6, 21, 107, and 47,176,870. Can you predict the next number? If you're left perplexed, you're in good company. These are the initial five busy beaver numbers, forming a sequence intricately linked to one of the most formidable questions in theoretical computer science. Determining the values of busy beaver numbers has been a daunting challenge that has captivated both professional and amateur mathematicians for over six decades.

Identification of Early Busy Beaver Numbers

Researchers identified the first four busy beaver numbers during the 1960s and 1970s. The significantly larger fifth number, denoted as BB(5), was only conclusively determined last year. This achievement was accomplished by a team primarily composed of amateur mathematicians collaborating within an online community known as the Busy Beaver Challenge.

The Elusive BB(6)

The magnitude of BB(6) remains unknown. All that exists are lower limits, which are truly astonishing. In 2022, busy beaver enthusiasts established that BB(6) is so large that it is practically impossible to write in ordinary decimal notation. Even if one were to somehow engrave a digit on every atom in the cosmos, there would not be enough atoms to make any meaningful progress. Scott Aaronson, a computer scientist at the University of Texas, Austin, remarked, “It’s way beyond anything that we could ever grasp or get our hands on.”

Recent Developments in BB(6)

Busy beaver hunters have now found that this already mind - boggling number must be even larger. One of the most mysterious and productive contributors to the Busy Beaver Challenge proved a new lower limit on BB(6) in June and shattered the record again just nine days later. These new results make the 2022 lower bound seem minuscule. William Gasarch, a computer scientist at the University of Maryland, stated, “Six is getting us into the stratosphere of large numbers.”

The Underlying Problem: The Halting Problem

The Halting Problem Defined

The challenging question behind the busy beaver numbers is as follows: Given the code of a computer program, can one determine whether it will eventually halt or run indefinitely? In 1936, the pioneering logician Alan Turing proved that there is no universal procedure for answering this question, which is now known as the halting problem. Any method that works for some programs will fail for others, and in certain cases, no method will be effective.

Turing Machines and the Busy Beaver Game

Turing proved this fundamental result by inventing a formal mathematical model of computation where programs are represented by hypothetical devices called Turing machines. Each Turing machine performs computations in discrete steps based on a unique set of simple rules. The more rules a Turing machine has, the more complex its behavior can become, and the more difficult it is to determine whether it will halt.

In 1962, the mathematician Tibor Radó introduced a novel approach to explore this question through what he termed the busy beaver game. To play, one first selects a specific number of rules, denoted as n. The objective is to find the n - rule Turing machine that runs the longest before eventually halting. This machine is called the busy beaver, and the corresponding busy beaver number, BB(n), represents the number of steps it takes.

Practical Difficulties in Finding Busy Beavers

In theory, to find the busy beaver for a given n, one needs to list all possible n - rule Turing machines, simulate the running of each machine using a computer program, identify and discard non - halting machines (such as those in infinite repeating loops), and record the number of steps taken by the halting machines. The machine with the longest run - time is the busy beaver.

However, in practice, this is extremely challenging. The number of possible machines grows exponentially with each additional rule. Analyzing each one individually is unfeasible, so custom computer programs are required to classify and discard machines. Some machines are easy to classify as they either halt quickly or fall into obvious infinite loops. But others run for an extended period without any discernible pattern, highlighting the difficulty of the halting problem. As more rules are added, more computing power is needed, and brute - force methods are insufficient. Clever mathematical techniques are required to measure the run - times of some machines. Shawn Ligocki, a software engineer and long - time busy beaver hunter, said, “Technology improvements definitely help, but they only help so far.”

The Quest for BB(6): A Historical Perspective

Early Efforts in the 1990s and 2000s

Busy beaver hunters began seriously tackling the BB(6) problem in the 1990s and 2000s, during a lull in the BB(5) hunt. Among them were Shawn Ligocki and his father, Terry, an applied mathematician who ran their search program during off - hours on powerful computers at Lawrence Berkeley National Laboratory. In 2007, they discovered a six - rule Turing machine with a record - breaking run - time. The number of steps it took before halting had nearly 3,000 digits, which, while colossal, could still be written down on a single sheet of paper in 12 - point font.

Kropitz's Contributions

Three years later, Pavel Kropitz, a Slovakian undergraduate computer science student, took on the BB(6) hunt as a senior thesis project. He developed his own search program and ran it in the background on a network of 30 computers in a university lab. After a month, he found a machine that out - ran the Ligockis' discovery. He then broke his own record after another month of searching, with a machine whose run - time had over 30,000 digits, filling about 10 pages.

Kropitz's machine held the BB(6) record for 12 years. Then, in May 2022, Shawn Ligocki, having access to a powerful computer cluster in his new job, decided to run his old code on the new hardware. He found a new champion, triggering a flurry of activity. Ligocki and Kropitz traded the record twice within two weeks, with Kropitz quickly beating Ligocki's new records each time. Ligocki recalled his father joking that Kropitz seemed to have already solved BB(6), always pulling out a slightly better machine.

The End of an Era

The last two machines discovered by Ligocki and Kropitz had run - times on an entirely new scale. To comprehend such large numbers, we must turn to advanced mathematical operations. Starting with addition and multiplication, repeated exponentiation leads to tetration, denoted by two upward - pointing arrows. Tetration grows extremely rapidly. For example, 10↑↑1 is 10, 10↑↑2 is 10 billion, and 10↑↑3 is 10 raised to the 10 - billionth power. When Ligocki beat Kropitz's record for the second time, it was with a six - rule Turing machine that ran for over 10↑↑5 steps before halting. Kropitz countered with a machine that ran for 10↑↑15 steps. Kropitz wrote, “That was the end of an era.” This was also the end of an era in terms of the nature of the busy beaver game, as until then, it had been a mostly individual competition, but the Busy Beaver Challenge soon changed that.

The Busy Beaver Challenge

Formation and Success with BB(5)

The Busy Beaver Challenge was founded in 2022 by Tristan Stérin, a computer science graduate student, with the aim of rigorously proving the true value of BB(5). In summer 2024, the group achieved this goal, with a crucial contribution from a mysterious newcomer known only as mxdys.

Doucette's Discovery and New Class of Machines

Katelyn Doucette, an undergraduate computer science student at Virginia Tech, saw news of the BB(5) result in Quanta and joined the Busy Beaver Challenge community. In May, she made an exciting discovery while looking through a list of “holdout” machines. With the help of Shawn Ligocki, she found a machine whose run - time was second only to Kropitz's champion. This machine belonged to a class of shift overflow counters, which achieve long run - times through a different mechanism. Ligocki said, “It’s exciting to see that these busy beavers have found a new technology.”

New Records and the Emergence of Shift Overflow Counters

Other busy beaver hunters had previously found shift overflow counters that halted after a long time, but Doucette's discovery made the team suspect there were more of these machines than they thought. Mxdys was the first to analyze other shift overflow counters and announced a new champion on June 16 that halted after 10↑↑107 steps. Kropitz graciously accepted the loss of his title, having also set a record for the longest - running seven - rule Turing machine a month earlier.

Beyond the Biggest: BB(6) and Unsolved Mysteries

New Records and Pentation

The new record for BB(6) didn't last long. A week later, mxdys broke it again with a machine whose run - time required the introduction of pentation, represented by three upward - pointing arrows. Pentation is repeated tetration. The number of steps mxdys' new champion took before halting was greater than 2↑↑↑5. This number is so large that even the more compact notation of towers of powers no longer fits in the universe.

The Antihydra and Unsolved Problems

This new result is only a lower limit on BB(6), and the true value could be higher. The team discovered a six - rule Turing machine named Antihydra last year, which almost certainly never halts, but researchers have been unable to prove it. Racheline, a busy beaver hunter, has shown that the question of whether Antihydra halts is related to the famous unsolved Collatz conjecture. Since then, many similar six - rule machines have been found. Solving these problems will require significant breakthroughs in pure mathematics.

However, for passionate busy beaver hunters, this is not a reason to be disheartened. There are still thousands of six - rule Turing machines to explore, each with its own fascinating behavior. Racheline wrote, “For me, the most valid reason to do math is because it’s fun. It is art. There will always be something new to do.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.