The busy beaver problem

Open In Colab

The busy beaver problem

Let \(BB(n)\) be the largest number of \(\one\)s produced by any \(\one\hash\)-program with \(\leq n\) instructions which halts properly.

Theorem 3

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

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

Proof. Suppose that the \(\one\hash\) program \(\mathtt{beaver}\) computed \(BB\).

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

\(\phifn_{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\), 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\). Then

\[\begin{split} \begin{array}{lclclcl} BB(N^2) & \geq & \phifn_{p_N}(\ ) & = & BB(N^2) + 1 \\ \end{array} \end{split}\]

Contradiction!

Exercise 41

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

Exercise 42

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

previous

The halting problem

next

Tiling