23 highlights
-
Programmers normally want to minimize the time their code takes to execute. But in 1962, the Hungarian mathematician Tibor Radó posed the opposite problem. He asked: How long can a simple computer program possibly run before it terminates? Radó nicknamed these maximally inefficient but still functional programs “busy beavers.”
-
“In math, there is a very permeable boundary between what’s an amusing recreation and what is actually important,” said Scott Aaronson, a theoretical computer scientist at the University of Texas, Austin
-
The logician Kurt Gödel proved the existence of such mathematical terra incognita nearly a century ago. But the busy beaver game can show where it actually lies on a number line, like an ancient map depicting the edge of the world.
-
The busy beaver game is all about the behavior of Turing machines — the primitive, idealized computers conceived by Alan Turing in 1936. A Turing machine performs actions on an endless strip of tape divided into squares.
-
If the square contains a 0, replace it with a 1, move one square to the right and consult rule 2. If the square contains a 1, leave the 1, move one square to the left and consult rule 3.
-
Turing proved that this simple kind of computer is capable of performing any possible calculation, given the right instructions and enough time.
-
As Turing noted in 1936, in order to compute something, a Turing machine must eventually halt — it can’t get trapped in an infinite loop. But he also proved that there’s no reliable, repeatable method for distinguishing machines that halt from machines that simply run forever — a fact known as the halting problem.
-
The busy beaver game asks: Given a certain number of rules, what’s the maximum number of steps that a Turing machine can take before halting?
-
For instance, if you’re only allowed one rule, and you want to ensure that the Turing machine halts, you’re forced to include the halt instruction right away.
-
But adding just a few more rules instantly blows up the number of machines to consider. Of 6,561 possible machines with two rules, the one that runs the longest — six steps — before halting is the busy beaver.
-
But some others simply run forever. None of these are the busy beaver, but how do you definitively rule them out? Turing proved that there’s no way to automatically tell whether a machine that runs for a thousand or a million steps won’t eventually terminate.
-
That’s why finding busy beavers is so hard. There’s no general approach for identifying the longest-running Turing machines with an arbitrary number of instructions; you have to puzzle out the specifics of each case on its own. In other words, the busy beaver game is, in general, “uncomputable.”
-
Proving that BB(2) = 6 and that BB(3) = 21 was difficult enough that Radó’s student Shen Lin earned a doctorate for the work in 1965.
-
William Gasarch, a computer scientist at the University of Maryland, College Park, said he’s less intrigued by the prospect of pinning down busy beaver numbers than by “the general concept that it’s actually uncomputable.” He and other mathematicians are mainly interested in using the game as a yardstick for gauging the difficulty of important open problems in mathematics — or for figuring out what is mathematically knowable at all.
-
The Goldbach conjecture, for instance, asks whether every even integer greater than 2 is the sum of two primes. Proving the conjecture true or false would be an epochal event in number theory, allowing mathematicians to better understand the distribution of prime numbers.
-
In 2015, an anonymous GitHub user named Code Golf Addict published code for a 27-rule Turing machine that halts if — and only if — the Goldbach conjecture is false.
-
Running this mindless machine isn’t a practical way to solve the conjecture, because we can’t know if it will ever halt until it does. But the busy beaver game sheds some light on the problem. If it were possible to compute BB(27), that would provide a ceiling on how long we’d have to wait for the Goldbach conjecture to be settled automatically.
-
In 2016, Aaronson established a similar result in collaboration with Yuri Matiyasevich and Stefan O’Rear. They identified a 744-rule Turing machine that halts if and only if the Riemann hypothesis is false.
-
For instance, the mathematician Pascal Michel proved in 1993 that the record-holding five-rule Turing machine exhibits behavior similar to that of the function described in the Collatz conjecture, another famous open problem in number theory.
-
Gödel’s famous incompleteness theorems of 1931 proved that any set of basic axioms that could serve as a possible logical foundation for mathematics is doomed to one of two fates: Either the axioms will be inconsistent, leading to contradictions (like proving that 0 = 1), or they’ll be incomplete, unable to prove some true statements about numbers (like the fact that 2 + 2 = 4).
-
The axiomatic system underpinning almost all modern math, known as Zermelo-Fraenkel (ZF) set theory, has its own Gödelian boundaries — and Aaronson wanted to use the busy beaver game to establish where they are.
-
In 2016, he and his graduate student Adam Yedidia specified a 7,910-rule Turing machine that would only halt if ZF set theory is inconsistent.
-
O’Rear subsequently devised a much simpler 748-rule machine that halts if ZF is inconsistent — essentially moving the threshold of unknowability closer, from BB(7,910) to BB(748).