Question

Question: Let$\mathit{\Gamma }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{\bigsqcup }\mathbf{\}}$ be the tape alphabet for all TMs in this problem. Define the busy beaver function $\mathit{B}\mathit{B}\mathbf{:}\mathit{N}\mathbf{\to }\mathit{N}$as follows. For each value of k, consider all K-state TMs that halt when started with a blank tape. Let$\mathit{B}\mathit{B}\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

BB is not a computable function

Step-by-step solution

Turing Machine(TM)

A Turing Machine is a computational model concept that runs on the unrestricted grammar of Type-0. It accepts recursive enumerable language and comprises of an infinite tape length, where reading and writing operations can be performed accordingly.

Proving BB is not computable

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

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

Now, construct a Turing Machine M which will halt if started with a blank tape as shown in the following steps:

1. M writes n times 1s on the tape.
2. M increases 1s to double on tape.
3. M runs F on the input $1^{2n}$. Therefore, M will always halt with $BB\left(2n\right)$when it starts with a blank tape.

We will run the 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 the maximum number of 1s that a$\left(n+c\right)$ stage Turing Machine will halt. This implies that$BB\left(n+c\right)⩾BB\left(2n\right)\forall n\dots \dots \dots \dots \dots \left(1\right)$

is monotonically increasing because$BB\left(n+1\right)⩾BB\left(n\right)\forall n\in N.$

But if that so then . This contradicts the above equation given in (1).

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