If there were any skeptical readers of my last column thinking to themselves “how on Earth are beavers related to fundamental mathematics,” I respond to them with: doubters be dammed! I hope this article will silence the (admittedly justified) skeptics by summarizing a rather remarkable story of mathematical insight, adversity, and community, with flashes of programming savviness and homages to the largest rodent in North America.
The story begins with the founder of computer science, Alan Turing, and his famous idealized machines, which helped codify several key elements of the theory of computation. Turing machines are theoretical devices consisting of an infinitely long piece of tape that’s split into square cells. Each cell contains a zero or one, and the machine performs operations on these cells in accordance with a certain number of rules. Each application of a rule is called a “step.”
Turing, with practical computation in mind, knew that it was important to determine whether a machine with a given set of rules would continue performing operations on the cells indefinitely or eventually halt, yielding some tangible outcome after a finite number of steps. In studying this halting problem, however, he realized that there is no systematic way to classify every machine as either halting or non-halting. In slightly more CS jargon, the halting problem is incomputable — there is no general algorithm that can say, based on any inputted Turing machine and rulebook, whether or not that machine will halt.
In the 1960s, three decades after Turing’s seminal work, Tibor Radó, a Hungarian mathematician who escaped Siberian prison after his capture during World War I, trekked across the Russian Arctic and eventually landed a professorship in the U.S., decided to look at Turing machines from a different perspective. He lumped Turing machines into categories based on the number of rules each one has and noticed something interesting.
More precisely, there is a special combination of rules such that the Turing machine runs for six steps before halting. This number is greater than any other Turing machine with two rules that halts in finite time. As a result, he deemed this special machine the two-state busy beaver in honor of the animal’s industriousness in building dams.
This of course can be generalized to any number of states: we define the nth-state busy beaver as the Turing machine with n rules which runs for longer than any other halting machine with the same number of rules. The busy beaver number, denoted as BB(n), is the number of steps this longest-running machine takes.
Because there’s no clear way of ruling out whether a machine halts though, the problem of finding the busy beaver and its associated number is extremely challenging. Allen Brady, a graduate of Oregon State University (whose mascot is the beaver), needed almost ten years to prove that BB(4) was equal to 107; part of his proof involved several calculations done via computers at a facility in Beaverton, Oregon. Recently, an online community of 20-plus contributors, many of whom without mathematics degrees, found BB(5) (which is 47,176,870), collaborating on Discord and utilizing software called Coq, which can verify the logic of mathematical proofs. The only thing known about BB(6) is that it must be greater than a number that contains more than 36,000 zeros after its significant figures.
But the utility of busy beaver numbers does not stop there. Mathematicians and theoretical computer scientists have derived a set of Turing machines that will halt if and only if certain famous open problems in mathematics are true. For instance, the unsolved conjecture by Goldbach, stating that every even whole number greater than 2 equals the sum of two prime numbers, is true if and only if a 43-state Turing machine halts in finite time. Similarly, if you can show that a certain 744-state Turing machine halts, then you would be a millionaire since that would prove the Riemann hypothesis, which has a prize of $1 million USD.
These results may indicate that busy beavers have applications to many different parts of mathematics despite being a niche problem in theoretical computer science. For this, Radó’s moniker is prescient, as beavers, along with being busy, are a keystone species, having an outsize impact on their entire ecosystem based on their specific skill set. The challenges surrounding the study of busy beavers have also brought together diverse groups of problem solvers, which is the most inspiring part of this story to me.
Mathematics ideally should bring people together through its shared language of numbers and universal theorems, as well as provide a creative outlet for enthusiasts of challenging problems. So, the next time you inevitably decry a math topic, try to think a little about ways in which the subject has helped you connect more with others (even if that connection is through collective frustration over a tough problem). It may make you busy, but the exercise will hopefully provide some more appreciation of math as you inevitably use it in your STEAM careers.
