4
$\begingroup$

I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable:

Find $\sum(n) = max \{\sum(M) | M \in M(n) \}$

Where

$n$ : Number of states

$M(n)$: Set of Turing Machines with $n$ states and binary alphabet (0s and 1s)

$[k]$: Configuration of having a block of $k$ consecutive 1s on an otherwise blank (All 0) tape, and with the head at the leftmost 1.

$e$: Empty tape (All 0s)

$\sum(M): \sum(M) = k$ if machine $M$ when started on $e$ halts with $[k]$. Otherwise $\sum(M) = 0$

The proof:

Suppose there is some Turing machine $\sum$ that computes $\sum(n)$. Then consider the following Turing machine $Q$ where $k$ is the number of states of the last 3 components:

Turing Machine

I cannot understand from here, what exactly is the contradiction here?

$\endgroup$
  • 3
    $\begingroup$ You managed to write $\Sigma(2k)+1$ using a machine with $2k$ states, which by definition of $\Sigma(n)$, can only write numbers up to $\Sigma(2k)$. $\endgroup$ – Ariel Dec 13 '15 at 22:05
  • $\begingroup$ Sorry, I'm really trying to understand; what's with doing that using Q? $\endgroup$ – Nubcake Dec 13 '15 at 22:14
  • 2
    $\begingroup$ If $\Sigma(n)$ is computable then you can construct the machine $Q$. $Q$ has $2k$ states (as explained in your proof, where $k$ is the number of states of the last 3 components). If $Q$ has $2k$ states, then the output of $Q$ on blank input satisfies $Q(\epsilon)\le \Sigma(2k)$, by denfition of the function $\Sigma(n)$. However $Q(\epsilon)=\Sigma(2k)+1$, contradiction. $\endgroup$ – Ariel Dec 13 '15 at 22:22
  • $\begingroup$ Why does Q have $2k$ states originally? $\endgroup$ – Nubcake Dec 13 '15 at 22:44
  • 2
    $\begingroup$ $k$ is the number of states in the last three components. Those states contain the sates of the machine "double", the states of the machine $\Sigma(n)$ which you assumed exists, and the states of the machine "+1". Since all parts are implementable, i can assume the machine implementing them has some number $k$ states. The machine $Q$ also writes "k" at the beginning, which can be done using $k$ states (as explained in the proof you provided), so you have a total of $2k$ states. $\endgroup$ – Ariel Dec 13 '15 at 22:51
4
$\begingroup$

I know it took me a few reads before a grasped what it was saying, so maybe if we build $Q$ in a different and (much) more verbose way, it'll help.

So let's start by assuming a Turing machine $\Sigma$ exist which, given a line of n 1's on an otherwise blank tape, can compute the busy beaver of n ($\Sigma(n)$) and write's out that many 1's on the tape. Now, this Turing machine has some number of states, which we will say is a.

Next, let's assume that another Turing machine, $+1$ which runs to the end of a line of 1's and adds one more 1 to that line. This Turing machine has some number of states, which we will say is b.

Next, let's assume that even another Turing machine exists, called $D$, short for Double. Given a tape with some number of 1's on it, it doubles the number of 1's on the tape. And let's say that it has some number of states c.

We now have three Turing machines, each with a, b, and c states respectively. So now let us define a number k, such that k = a + b + c.

Now let us build another Turing machine, $K$, short of Write K. $K$ will print out k 1's on a blank state, and have k states. A simple machine, where each state writes 1, moves to the next position on the tape, and then goes to the next state.

So now let's combine all our machines into one big machine.

We start with $K$, then go to $D$, then $\Sigma$, and finally $+1$. Let's call it $Q$. Now, to find the number of states $Q$ has, you have to add up the members. In order, that is k + c + a + b. And given that a + b + c = k, this mean that $Q$ has 2k states.

Now, let's run $Q$ and see what happens.

We start with a blank tape. Then $K$ runs and puts k 1's on the tape. Next, $D$ doubles this tape in size, so it now has 2k 1's on the tape. Next, $\Sigma$ runs and computes $\Sigma(2k)$ and prints that many 1's on the tape (replacing the 2k 1's). Finally, $+1$ runs and adds one extra 1 on the end of the line. So there are now $\Sigma(2k) + 1$ 1's on the tape.

Now, this means that $Q$, a Turing machine with 2k states, just wrote $\Sigma(2k) + 1$ 1's on a tape, which is impossible because the maximum number of 1's possible to write on a tape, given 2k states (and not counting cases that never halt), is $\Sigma(2k)$. Contradiction (and thus $Q$ cannot exist, and namely $\Sigma$ inside of $Q$ cannot exist).

In short, $Q$ has 2k states because we purposefully built it to have exactly 2k states to aid in creating the contradiction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.