The Busy Beaver Problem

Let's call this function F(n). F(n) definitely exists, as there are only finitely many n-state Turing machines, so some of them must print the maximal number of ones (we exclude non-halting Turing machines from consideration as they're not of great interest).

We can prove that it can't be computed as follows:

Let B be a Turing machine with n states that prints out F(n) ones on its tape before halting, i.e. it's an ultimately busy beaver.

Now consider a Turing machine that computes F(n), using q states, when given n in binary on its tape. Call this machine Y. Then get machines X, which takes an empty tape and prints n on it (in binary), and Z, which takes a number in binary and outputs the same number in unary. So the compound machine XYZ takes an empty tape and prints F(n) ones on it, just like machine B.

The thing is, machines Y and Z require only a constant number of states (say a and b respectively), and machine X needs log (n) states (base 2). So XYZ has log (n) + a + b states altogether. This means that for any integer n > log(n) + a + b, XYZ computes F(n) using fewer states than B. The thing is, it's easily shown (I'm told) that F(n) > F(m) for n > m, so we've got a contradiction. XYZ must not exist. But X and Z definitely exist, so we reluctantly concede that Y never existed at all. So F(n) cannot be computed.

What's so great about that?

Well, the thing is, F(n) grows faster than any function anyone can compute, for example 2 to the nth to the nth to the nth. Not only that, but for any computable function g, g(F(n)) < F(n+1) for infinitely many n. So, for example, for infinitely many (~= large enough) n, F(n) to the power F(n ) to the power F(n) .... as many times as you like, is < F(n+1).

It has been computed in specific cases, for small n:

n F(n) 1 1 2 4 3 6 4 13 5 >= 4098 6 >= 95524079

Some people reckon F(5) will never be exactly computed. The inherent difficulty in computing F(n) can be appreciated if we think of a Turing machine that could prove Fermat's Last Theorem or the Goldbach conjecture. These machines need not be inordinately large, having n states for some reasonable n; if we could compute F(n) we'd know how long to wait for these machines to halt and thus, in theory, whether or not the conjecture is true. This is only an introduction to this wonderful function, based on material from The Turing Omnibus by A.K. Dewdney. Heiner Marxen, who established (along with Jürgen Buntrock) lower bounds on F(5) and F(6), has a Busy Beaver page and Michael Somos has a Busy Beaver Turing Machine page.