An informal group of math enthusiasts has moved on to a bigger and potentially far more difficult challenge after hitting a major milestone last summer when they definitively answered a question about program behavior that had persisted for more than three decades. The success of the project in eliminating billions of different programs designed to run on a Turing machine to finally uncover which one would run longest before halting gracefully has led senior mathematicians to consider how crowdsourcing could work on other large-scale problems.
The Busy Beaver Challenge group, founded by Tristan Stérin, a computer science researcher at the University of Maynooth in Ireland, in early 2022 coordinated their results through a combination of the Discord chat service, a wiki, and Github’s code repository. With the help of these collaboration tools, the group built on existing work by people working mostly independently and supplying results to a central repository. In doing so, they attacked one of the oldest problems in computer science: how to work out when, and indeed whether, any program will terminate.
As computing pioneer Alan Turing found when constructing the thought experiment that led to his eponymous machine, there is no general way to determine whether any program will stop in the near or distant future, or just keep going forever. Recognizing that there is no general solution, mathematicians and computer scientists have looked at ways to attack it by breaking the problem down into more manageable pieces.
In the 1960s, Hungarian mathematician Tibor Radó coined the term “busy beaver” as the name for a simple Turing-machine program that eventually halts, but only after generating huge amounts of output or taking an incredibly long time. To run for a long time, sliding along a tape as it reads and writes values, and still be able to enter a state that brings it to a final halt implies a chaotic system. Only hitting a rare sequence of state transitions can bring the program to its final stop.
Researchers quickly found as the number of program states increases, the length of the printed tape increases at an extraordinarily rapid pace. A binary machine that can switch between two states, which implies a four-entry truth table, prints no more than six bits unless its program winds up in an infinite loop. If you move to a four-state machine, denoted as BB(4,2), the longest-program will not stop before printing a hundred bits. With BB(5,2), the addition of a fifth state pushed this way further. The Busy Beaver Challenge group proved in 2024 it stands at 41,176,870.
Machines that that can print more than binary seem to grow even more quickly. BB(2,4), a busy beaver that has two states but can print out four different symbols, produces an output 20 times longer than BB(4,2). The champion of BB(2,5) is a machine that only halts after printing 590 trillion digits, seven orders of magnitude more than BB(5,2).
Identifying these winning beavers calls for a divide-and-conquer strategy to eliminate all that never halt and to focus on those that can. This process of elimination is why having identified the winning program at the end of the 1980s, Berlin-based software engineer Heiner Marxen and colleague Jürgen Buntrock had to wait more than three decades to see it crowned.
The elimination work has established a zoology of non-halting programs, which has helped to identify and eliminate them. As its name suggests, the Bouncer moves between two walls that, if they do not run out of steam quickly after starting, expand outwards in both directions along the tape. Timeline diagrams of Bouncer behavior resemble slowly growing trees. Cyclers, on the other hand, fall into a regular, ever-repeating pattern that can be complex, but which offers no way out. Translated Cyclers perform much the same way but repeat their patterns on different parts of the tape, often moving gradually in one direction along the tape. This added characteristic makes them tougher to spot than Cyclers.
Detecting whether these and other programs get stuck in infinite loops calls for a combination of formal analysis and accelerated simulation. Marxen and Buntrock developed a way of grouping repeated sequences into linked lists of blocks that could be processed at a higher level. Though he did not publish the work, Marxen came up with a further enhancement he explained in the mid-2000s to Challenge collaborator Shawn Ligocki, a data engineer at Cornell University’s Center for Avian Population Studies and who has been hunting busy beavers for 20 years.
The compressed tape language that Ligocki adapted uses ideas from the regular expressions used for text processing. These provide a way to group sequences that do not repeat exactly into identifiable patterns. If all the possible outputs can fit into one regular expression, it indicates the machine will never halt. In the BB(5,2) work, the team used this technique to show more than a million Turing machines would never halt.
“It does not attempt to show what the Turing machine will do. Instead, it shows what it will never do,” Ligocki said.
What remains from this process of elimination are holdouts: the programs that defy broader analysis methods. Before the Challenge group confirmed the winner, some mathematicians thought the BB(5,2) class of machines contains the worst kind of holdout: a “cryptid.”
Cryptids seem as though they could terminate, but only after a practically uncountable number of iterations, if at all. This combination of properties mimics a long-standing conjecture in mathematics posed by Lothar Collatz in 1937. Collatz’s original conjecture involved an iterative function that divides even numbers by two but multiplies odd numbers by three before adding a one. If the conjecture is correct, whatever the input, the function’s ultimate value is 1.
Cryptids display seemingly erratic behavior. Worse, predicting their final state, if one exists, would require a solution equivalent to proving Collatz’s original conjecture. That is a problem beyond the reach of current mathematics, said Pascal Michel, a longstanding busy-beaver researcher now retired from his position at the Jussieu Mathematics Institute in Paris, France.
Not all Collatz-like functions are cryptids, however. Some of these simulators of arithmetic sequences have given up their secrets. The highest scorers in both the BB(5,2) and BB(2,4) categories do not just obey a Collatz-like sequence, but share the same core pattern. “This trajectory appears to be ubiquitous among Turing machines around this size,” Ligocki said.
Based on findings like these, it is easy to assume that future winners will also be Collatz-like. However, team members are only too aware of becoming too focused on particular types of program. Ligocki notes, “For BB(6,2) it feels we have a significant selection bias. The longest-running Turing machine [so far] is structured. But that is because we cannot simulate a machine for that long without structure. The worst example of this in BB(5,2) was Skelet #1.”
It took the creation of a custom accelerated simulator by Ligocki and fellow group member Pavel Kropitz to show the machine at its heart is a Translated Cycler. Proving its behavior required more than 1,600 lines of Coq code. “There will be thousands of machines like this in BB(6,2) and we don’t yet have a clear idea how to generalize our simulator,” Ligocki adds.
Michel has noted in his long-running survey of busy-beaver results that those that run many steps on small sections of tape do not resemble Collatz functions. But they, too, can be champions, as shown by several classes of busy beaver that print more than two types of symbol. “For a long time, I thought that Collatz-like behavior would be the rule for busy-beaver champions. Now, I think that I was wrong,” he said.
Thanks to the automated tools, the raw number of holdouts yet to be analyzed in depth were more than halved from around 12,000 in less than six months after the team moved on from the completed BB(5,2). However, even when they are not cryptids, holdouts in this class of machine present additional levels of difficulty. The current reigning champion for BB(6,2), discovered by Kropitz, is a machine that could print a tape with more digits than there are particles in the known universe before halting. But it proved amenable to a hand-generated proof.
The continuing work is providing inspiration for ways to crowdsource solutions to large-scale math problems. Terence Tao, professor of mathematics at the University of California at Los Angeles, hopes to tap the experience of many math enthusiasts and researchers in a project of his own. Like the work in the Busy Beaver Challenge, the project takes aim at an entire class of algebraic properties, where individuals can work on discrete sub-problems. Like the halting problem that lies at the heart of the Busy Beaver Challenge, the overall question that Tao is dealing with is undecidable. Yet in the same way, he hopes there will be “interesting problems and phenomena to discover before we reach that threshold.”
The open question for beaver hunters is whether BB(6,2) will yield a definite answer. Michel expects the situation to lead to the situation where there will be a strong candidate for champion, but only on the condition that known cryptids the group and others find are assumed to never halt. A more definite result, however, would mean an incredible breakthrough in mathematics because it would shed a new light on the Collatz conjecture at the very least.
Further Reading
- Aaronson, S.
The Busy Beaver Frontier, ACM SIGACT News, Vol. 51, No. 3, September 2020 - Michel, P.
The Busy Beaver Competition: A Historical Survey, arXiv:0906.3749v7, Version 7, November 2022 - Marxen, H. & Buntrock, J.
Attacking the Busy Beaver 5, Bulletin of the EATCS, Number 40, February 1990, pp. 247-251. https://turbotm.de/~heiner/BB/mabu90.html - Xu, C.
Skelet #17 and the fifth Busy Beaver number, arXiv:2407.02426, July 2024 - BB Challenge wiki: https://wiki.bbchallenge.org/
Join the Discussion (0)
Become a Member or Sign In to Post a Comment