It's OK, this isn't about real beavers of any sort, but about Turing machines with a special talent for making the most out of what they are given.

As long as you know what a Turing machine is, the Busy Beaver problem is one of those wonderfully simple problems that turns out to have deep and surprising connections and implications. It is very easy to understand. The question it answers is, given a Turing machine of a given size, what is the longest run time, i.e. number of steps, before the machine halts. It's a sort of inverse code golf for Turing machines. Notice that Turing machines that don't halt don't count because they run for an infinite number of steps.

There are various ways of limiting the size of the Turing machine, but the most general is to restrict it to n states and what it can write to the tape to m symbols. Thus the function we would like to evaluate is BB(n,m) which is the maximum number of steps possible for an n state Turing machine using m symbols.

For small n and m we can fairly easily work out BB(n,m), for example:

The state diagram for the BB(3,2) machine (note the halting state H is extra to the three computing states):

all seems reasonable but then we have:

where the ? means this is the largest value found so far. At the moment BB(4,2) is the largest value of n for which BB is known.

What is even more surprising is that:

Notice that's 10 raised to the (10 (raised to the 10) (raised to the 10))) or

which is 10 followed by 10,000,000,000 zeros. To make this easier to write down, Knuth invented the up arrow notation:

The latest result, and the event that prompted this news, is that after 12 years of no progress on the problem we have:

which is a number so large that, as Shawn Ligocki the author of the breakthrough machine that started the ball rolling, was forced to remark:

(it)  can no longer be stored directly in binary in computer memory. In fact, I cannot even tell you how many digits these numbers have or even the number of digits that [the number of digits] has without using a special notation.

Is the Busy Beaver problem at all important, rather than just being fascinating?

Consider the halting problem - i.e. does a given Turing machine with n states halt when run on a tape with m symbols - which is non-computable. Now suppose we have all values of BB(n,m) we can use this to solve the halting problem because we know that a machine with n states and m symbols has to halt in BB(n,m) steps - so run it for BB(n,m) steps and if it hasn't stopped then it doesn't ever halt. This implies that for general n, m BB has to be non-computable - if it was computable the halting problem would be computable and it isn't.

You can use the same argument for any mathematical problem that conjectures that something is always possible without saying how. For example, the Goldbach conjecture, i.e. every even number is the sum of two primes, can be tested by writing a program that tests each possible number in turn and stops when it finds the first exception. This program is equivalent to an n state Turing machine working on an m symbol tape so we know it has to halt in at most BB(n,m) steps - so run the program for BB(n,m) steps and if it is still going then the Goldbach conjecture is true.

None of this is likely to be of practical value, however, because the BB function is very difficult to work out and it increases  so rapidly that running any program for that number of steps is not a physical possiblity.

What the BB function does do for us is to indicate how quickly behavior becomes far more complex than the machine that creates it. That simple binary machine with just 6 states can run for 10^^15 states before halting is astonishing.

Programmer's Guide To Theory - The Halting Problem

Computing With Trains - Turing's Trains

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Apache HOP 2.0 Released 13/06/2022 Apache Hop 2.0 has been released. The Hop orchestration platform is an open source data integration platform in which everything is treated as metadata, meaning it can work with most data platfor [ ... ]

Apache Hop 2.0 has been released. The Hop orchestration platform is an open source data integration platform in which everything is treated as metadata, meaning it can work with most data platfor [ ... ]

John Kemeny, born in Hungary on May 31st 1926, was the co-author of BASIC, standing for Beginner's All-purpose Symbolic Instruction Code. Although it is thought of as the popular language of [ ... ]

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info