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 13

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

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

Proof. We are going to prove this two ways. Our first proof uses the Recursion Theorem.

Suppose that we had a program \(\mathtt{beaver}\). Let \(q\) be a program so that for all \(p\),

\[ [\![ q]\!](p) = [\![\mathtt{beaver}]\!](|p|) + \mathtt{1}, \]

where \(|p|\) is the number of instructions in \(p\). The function \(p\mapsto |p|\) is computable. So \(q\) is computable. By the Recursion Theorem, there is some \(p^*\) so that

\[ [\![ p^* ]\!](\ ) \simeq [\![ q]\!](p^*) = [\![\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.

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 \one^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 70

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

Exercise 71

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

Exercise 72

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?