Question

Let $\Gamma =\left\{0,1,\sigma \right\}$be the tape alphabet for all $TMs$ in this problem. Define the busy beaver function $BB:N\to N$ as follows. For each value of $K$, consider all $K$-state $TMs$ that halt when started with a blank tape. Let$BB\left(k\right)$ be the maximum number of$1s$ that remain on the tape among all of these machines. Show that$BB$ is not a computable function.

Short answer

It is proved that $BB$is not computable function

Step-by-step solution

Turing Machine(TM)

A Turing Machine is computational model concept that runs on the unrestricted grammar of Type-0. It accepts recursive enumerable language. It comprises of an infinite tape length where read and write operation can be perform accordingly.

Proving BB is not computable

Assume that, $BB$is a computable function. Now if that so, then there must exist a Turing Machine $F$that will compute $BB$.

So,$F$ be $TM$that halts with $1^{BB\left(n\right)}$on the tape on input:$1^n$for all value of ‘$n$’.

Now construct Turing Machine $M$which will halt if started with a blank tape as follows steps:

1. $M$write n times $1s$on the tape.
2. $M$increase $1s$ to double on tape.
3. $M$run $F$on the input $1^{2n}$. Therefore, $M$will always halt with$BB\left(2n\right)$ when it is started with a blank tape.

We will run 1st step up to$n$ times which correspond to ‘$n$’ states. And we have to run step 2 and step 3 for some constant state ‘$c$’.

So according to this,$BB\left(n+c\right)$ is maximum number of$1s$ that a$\left(n+c\right)$ stage Turing Machine will halt

This implies that:

$BB\left(n+c\right)\ge BB\left(2n\right)\forall n.........\left(1\right)$

$BB$is monotonically increasing because

$BB\left(n+1\right)\ge BB\left(n\right)\forall n\in N$

But if that so, then$BB\left(n+c\right){\left(BB\left(2n\right)\forall n\right)}^c$ . This is contradicting to above equation given in (1).

Hence conclude that$BB\left(k\right)$ is not computable function.