Busy beaver hunters reach numbers that overwhelm ordinary math

Summary

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) hu...