But how difficult is it? In 1962, the mathematician Tibor Radó invented a new way to explore this problem Busy beaver game. To play, first select a specific number of rules – add that number n. Your goal is to find n– Lending Turing machine, running for the longest before it finally stops. This machine is called the Busy Beaver, and the corresponding Busy Beaver, BB (n) is the number of steps it takes.
In principle, if you want to find a busy beaver for any given busy beaver nyou just need to do some things. First, list all possible n– Tuli Machine. Next, use a computer program to simulate running each computer. Looking for obvious signs that machines will never stop, for example, many machines will fall into infinite repetitive cycles. Discard all these non-isolators. Finally, record the steps taken by each other machine before stopping. The one that runs the longest is your busy beaver.
Actually, this gets tricky. For beginners, the number of possible machines grows rapidly with each new rule. Analyzing them individually will be hopeless, so you need to write a custom computer program to classify and discard the machine. Some machines are easy to sort: they either stop quickly or fall into an easily identifiable infinite loop. But the others ran for a long time without showing any obvious patterns. For these machines, stopping the problem should get a terrible reputation.
The more rules you add, the more computing power you need. But brute force is not enough. Some machines run for so long before they stop, it is impossible to simulate them step by step. You need clever math skills to measure their runtime.
“Technical improvements will certainly help,” Shawn Ligockisoftware engineer and long-heavy beaver hunter. “But they only have helped so far.”
The end of the era
During the 1990s and 2000s, during the deadlock of BB(5) Hunt, busy beaver hunters began to seriously solve the BB(6) problem. These include Shawn Ligocki and his father Terry, an applied mathematician, who planned a search program on a powerful computer at the Lawrence Berkeley National Laboratory. In 2007, they found a six-scale Turing machine that broke the record of the longest run time: taking nearly 3,000-digit steps before stopping. By any ordinary measure, this is a huge number. But that’s not to write it down. In a 12-point font, these 3,000 digits will cover a piece of paper.
Three years later, Pavel Kropitz, an undergraduate computer science student at the University of Slovakia, decided to use BB (6) Hunter (6) as a senior thesis project. He wrote his own search plan and set it up to run on a network of 30 computers in a university lab. A month later, he discovered that one machine had a much longer run time than the one Ligockis discovered.
“I’m lucky because people in the lab have complained about my CPU usage and I have to cut it down a bit.” Busy Beaver Challenge Server. After another month of searching, he broke his own record with a machine that had 30,000 digits of running time and could fill in about 10 pages.
