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:

BB(2,2)=6

BB(3,2)=21

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

BB(4,2)=107

all seems reasonable but then we have:

BB(5,2)=? 47176870

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:

B(7,2)>10^10^10^18705353

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

10^10^10= 10^10,000,000,000

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

10^^3=10^10^10

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

BB(6,2) >10^^15

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.

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way. His more recent book is The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, examines the nature of programming and reveals why it is a very special skill.

More Information

BB(6, 2) > 10↑↑15

Related Articles

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.

Comments

Make a Comment or View Existing Comments Using Disqus

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

<ASIN:1871962439> 

<ASIN:1871962722>