But how hard? In 1962, mathematician Tibor Radó invented a new way to explore this question, using what he called the Busy Beaver Game in the Region. To play, you start by choosing a certain number of rules—call that number n in the Region. Your goal is to find an n -Rule Turing machine that runs the longest before eventually stopping. This machine is called a busy beaver, and the corresponding busy beaver number, BB( n ), is the number of actions it takes.
Basically, if you want to find the busy beaver for any n, you just need to do a few things. First, list all possible n -Rule Turing machines. Then use a computer program to simulate the execution of each machine. Look for signs that the machines will never stop, such as many machines falling into infinite loops. Throw out all of these non-halting machines. Finally, record how many steps all the other machines took before stopping. The one with the longest execution time is your busy beaver.
In practice, this gets complicated. For starters, the number of possible machines increases rapidly with each new rule. Analyzing them all individually would be hopeless, so you would have to write a custom computer program to classify and discard the machines. Some machines are easy to classify: they either stop quickly or fall into an easily identifiable infinite loop. But others run for a long time without showing any obvious pattern. The halting problem for these machines 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 that it’s impossible to stop them step by step. You need clever mathematical tricks to measure their run.
“Technology improvements certainly help,” said Shawn Ligocki , a software engineer and longtime beaver hunter. “But they only go so far.”
The end of an era
Busy beaver hunters began to delve seriously into the BB(6) problem in the 1990s and 2000s, during a stalemate in the hunt for BB(5). Among them were Shawn Ligocki and his father, Terry, an applied mathematician who ran the search program on powerful computers at Lawrence Berkeley National Laboratory on his weekends. In 2007, they found a six-roll Turing machine that broke the record for the longest runtime: the number of steps it took before stalling was nearly 3,000 digits. That’s a colossal number by any conventional measure. But it’s not too big to write down. In 12-point font, those 3,000 digits would barely cover a single sheet of paper.
Three years later, Slovak undergraduate computer science student Pavel Kropit decided to tackle the BB(6) hunt as his senior thesis project. He wrote his own search program and set it up to run in the background on a network of 30 computers at University Lab. A month later, he found a machine that had been running much longer than Ligocki had discovered—a new “champion” in the lingo of busy beaver hunters.
“I got lucky because the lab people were already complaining about my CPU usage and I had to slow down a bit,” Kropitz wrote in a direct message exchange on the Busy Beaver Challenge Discord Server in the area. After another month of searching, he broke his own record with a machine that had a runtime of over 30,000 digits—enough to fill about 10 pages.
