The thing about the BusyBeaver function is that it is very easy to understand, but very difficult to compute. We now know its value up to 5, which isn't much progress for more than 50 years work.

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 working with just two symbols of a given size,  where size is measured as the number of possible states, 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. This is an important point because a Turing machine with a small number of states can run for a long time simply by cycling between states, but the requirement for the machine to stop means something has to be changing so that a stop condition can be met. Consider the problem of writing a program with a small number of statements such that it does eventually stop - what is the maximum run time?

In the 1960s it was quickly proven that BB(1)=1, BB(2)=6 and BB(3)=21. The small number of states made it possible to do a complete search. It then took until 1983 for Allen Brady to work out that BB(4)=107 and here is the the state diagram for the Turing machine that runs for BB(4):

After that all went quiet, despite many people beavering away at the problem. 

Notice that BB(n) must be "difficult" to compute because if it was possible to write down a formula for it then the halting problem would be solved. If you want to know if an n-state Turing machine halts simply run it and see if it is still going after BB(n) states. If it is, then it will never halt as BB(n) is the maximum number of state transitions a halting machine can perform. Notice that this doesn't rule out being able to compute BB(n) for any given n - the non-computability result means that you cannot provide a computation that works for any and all n.

Finite or bounded things are always computable. For example, if you limit the size of the the Turing machine to n then the halting problem is computable for that n. It is only when you demand a solution for all n, or better unbounded n, that the problem becomes non-computable.

Now we have the result stated in the headline:

BB(5)=47,176,870.

That is, the longest a five-state Turing machine can run for is 47,176,870 steps or state transitions.

The result was finally proved by an international collaboration called bbchallenge which set about the task using the Coq proof system. There are roughly (4n + 4)²ⁿ  Turing machines on n states and this makes the number of machines for n=5:

10,240,000,000,000

Then there is the problem of how long to wait before deciding that a machine isn't going to halt. A machine with 5 states, discovered by Jürgen Buntrocka, runs for exactly 47,176,870. This was the champion machine and if no five-state machine, that halts, could be found that gives a bigger value we have solved the problem. Put another way, if a machine runs for longer than the champion then it either doesn't halt or it becomes the new champion.

Interestingly the machine that runs for BB(5) is a five-state machine that computes:

• g(x) = (5x+18)/3 if x = 0 (mod 3),
• g(x) = (5x+22)/3 if x = 1 (mod 3),
• g(x) = HALT if x = 2 (mod 3).

(Shtetl-Optimized)

If you know the Collatz Conjecture you will recognize that this is very similar - and in this case it provably reaches HALT.

So now the team is focusing on computing BB(6) and it seems likely that this will never be completed as the number of machine on six states is large and we already know that BB(6) is at least 10 raised to the power of 10 fifteen times. 

What is the point of all of this?

To explore the edges of what is computable and how fast complexity grows when simple systems scale? No not really, it is just fun...

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

[July 2nd 2024] We have proved “BB(5) = 47,176,870”

Related Articles

Busy Beaver 6,2 Is Just Too Big!

Programmer's Guide To Theory - The Halting Problem

Computing With Trains - Turing's Trains

Terry Tao Almost Proves Collatz Conjecture

Collatz conjecture proved?

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