The busy beaver problem

Let \(BB(n)\) be the largest number of 1s produced by any 1#-program with at most \(n\) instructions which halts properly on all empty registers. Notice that \(BB\) is well-defined and total. The main point is that \(BB\) is not computable.

Theorem 14

There is no program \(\mathtt{beaver}\) such that for all \(n\)

\[ \begin{array}{lcl} [\![\mathtt{beaver}]\!](\onett^n) & = & \onett^{BB(n)} \end{array} \]

Proof. We are going to prove this two ways. Our first proof uses the Recursion Theorem in the guise of reflective \(\onesharp\).

Suppose that we had a program \(\mathtt{beaver}\) as described above. Let \(p\) be a program which writes itself to R1, then takes it length (its number of instructions), applies \(\mathtt{beaver}\), and finally adds a \(\onett\) at the end. Thus

\[ [\![ p ]\!](\ ) \simeq [\![\mathtt{beaver}]\!](|p|) + \mathtt{1} = \mathtt{1}^{BB(|p|) + 1} \]

But by definition of \(BB\), for all programs \(r\), if \([\![ r ]\!](\ ) \simeq \mathtt{1}^k\), then \(k \leq BB(|r|)\). Taking \(r\) to be \(p\), we see that

\[ BB(|p|) + 1 \leq BB(|p|), \]

and this is a contradiction. So there can be no program \(\mathtt{beaver}\).

Proof. Here is a second proof. Suppose that the \(\one\hash\) program \(\mathtt{beaver}\) computed \(BB\) as above.

Let \(\mathtt{square}\) be a \(\one\hash\) program to compute \(n \to n^2\), using unary notation.

Consider the programs \(p_{n}\) for \(n\in N\), given by

\[ p_n \quadeq (\one\hash)^{n} + \mathtt{square} + \mathtt{beaver} + \one\hash \]

Then \([\![ p_n]\!](\ )\simeq \onett^K\), where \(K = BB(n^2) + 1\).

Notice that the number of instructions in \(p_n\) is linear in \(n\). In fact, it is \(n + m +1\), where \(m\) is the total number of instructions in \(\mathtt{square}\) and \(\mathtt{beaver}\).

Let \(N\) be large enough so that \(N^2 > N+m+1\). Then by definition of \(p_N\),

\[\begin{split} \begin{array}{lcl} |[\![ p_N]\!](\ )| & = & BB(N^2) + 1 \\ \end{array} \end{split}\]

On the left above, we mean the number of symbols in \([\![ p_N]\!](\ )\).

The number of instructions in \(p_N\) is \(N+m +1 < N^2\). So by definition of \(BB\), \(BB(N^2)\) is at least \(|[\![ q]\!](\ )|\), for any program of length \(\leq N^2\) which happens to produce an output which is all \(1\)’s. And \(p_N\) is one such program. Hence we also have

\[ BB(N^2) \geq |[\![ p_N]\!](\ )| \]

This is a contradiction!

Exercise 99

Our first proof did not exactly prove that \(\onehash\) has no program \(\mathtt{beaver}\) (It showed that reflective \(\onehash\) has no such program.) How would we change the argument to get that result? (There are several ways to do this.)

Exercise 100

Show that there is no total computable function \(f\colon\N\to\N\) such that for all \(m\), \(f(m) \geq BB(m)\).

Exercise 101

A common estimate for the number of atoms in the universe is \(M = 10^{82}\). Show that \(BB(50) > M\).

Exercise 102

We defined \(BB(n)\) using 1# programs with at most \(n\) instructions. How would things change if we defined \(BB(n)\) using programs with at most \(n\) symbols?