But just how much harder? In 1962, the mathematician Tibor Radó invented a new way to explore this question through what he called the busy beaver game. To play, start by choosing a specific number of rules — call that number n. Your goal 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), is the number of steps that it takes.
In principle, if you want to find the busy beaver for any given n, you just need to do a few things. First, list out all the possible n-rule Turing machines. Next, use a computer program to simulate running each machine. Look for telltale signs that machines will never halt — for example, many machines will fall into infinite repeating loops. Discard all these non-halting machines. Finally, record how many steps every other machine took before halting. The one with the longest runtime is your busy beaver.
In practice, this gets tricky. For starters, the number of possible machines grows rapidly with each new rule. Analyzing them all individually would be hopeless, so you’ll need to write a custom computer program to classify and discard machines. Some machines are easy to classify: They either halt quickly or fall into easily identifiable infinite loops. But others run for a long time without displaying any obvious pattern. For these machines, the halting problem deserves its fearsome reputation.
The more rules you add, the more computing power you need. But brute force isn’t enough. Some machines run for so long before halting that simulating them step by step is impossible. You need clever mathematical tricks to measure their runtimes.
“Technology improvements definitely help,” said Shawn Ligocki, a software engineer and longtime busy beaver hunter. “But they only help so far.”
End of an Era
Busy beaver hunters started chipping away at the BB(6) problem in earnest in the 1990s and 2000s, during an impasse in the BB(5) hunt. Among them were Shawn Ligocki and his father, Terry, an applied mathematician who ran their search program in the off hours on powerful computers at Lawrence Berkeley National Laboratory. In 2007, they found a six-rule Turing machine that broke the record for the longest runtime: The number of steps it took before halting had nearly 3,000 digits. That’s a colossal number by any ordinary measure. But it’s not too big to write down. In 12-point font, those 3,000 digits will just about cover a single sheet of paper.
Three years later, a Slovakian undergraduate computer science student named Pavel Kropitz decided to tackle the BB(6) hunt as a senior thesis project. He wrote his own search program and set it up to run in the background on a network of 30 computers in a university lab. After a month he found a machine that ran far longer than the one discovered by the Ligockis — a new “champion,” in the lingo of busy beaver hunters.
“I was lucky, because people in the lab were already complaining about my CPU usage and I had to scale back a bit,” Kropitz wrote in a direct message exchange on the Busy Beaver Challenge Discord server. After another month of searching, he broke his own record with a machine whose runtime had over 30,000 digits — enough to fill about 10 pages.
Kropitz’s machine held the BB(6) record for 12 years. Then, in May 2022, Shawn Ligocki started a new job where he had access to a powerful computer cluster, and he decided to try running his old code on newer hardware. Sure enough, he found a new champion that beat Kropitz’s record. The discovery kicked off a flurry of activity. Twice in the span of two weeks, Ligocki announced a new champion on a busy beaver mailing list. Each time, Kropitz beat his record within three days. Ligocki remembers his father marveling at how Kropitz pulled it off.
“He was joking that he imagines Pavel has already solved BB(6),” Ligocki said. “Whenever we find a champion, he just goes and pulls out of his bag one that’s a little bit bigger.”
But the last two machines that Ligocki and Kropitz discovered didn’t run just a bit longer than the reigning champion — their runtimes were on an entirely new level.
To understand numbers this large, we need to go back to the familiar mathematics of addition and multiplication. Start by adding up n copies of a number — that’s just the definition of multiplication by n. If you instead multiply n copies of a number, that’s known as exponentiation. So what happens if you repeatedly exponentiate a number? That process defines a new operation called tetration, denoted by two arrows pointing up.
Tetration gets big fast. $latex 10 uparrowuparrow 1$ is just 10. But $latex 10 uparrowuparrow 2$ is 1010, or 10 billion, and $latex 10 uparrowuparrow 3$ is 10 raised to the 10-billionth power: a 1 followed by 10 billion zeros. To write out all the digits you’d need a stack of paper a thousand feet high. At $latex 10 uparrowuparrow 4$, you cross a symbolic threshold where it’s no longer a matter of finding enough paper — there are far more digits than atoms in the universe.