Busy Beaver problem - Proof by contradiction

Question

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:

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

Answer 1

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.