Uncomputability of Busy Beaver Function

Question

https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S.28n.29_and_.CE.A3.28n.29

So this is wikipedia's proof of why Busy Beaver Function is uncomputable. But I don't get two things.

1. How do you know that < Create_n0 | Double | EvalS | Clean > has $N$ states? I understand that < Create_n0 | Double | EvalS > has $N$ states but I don't understand why adding Clean doesn't change the number of states.

2. Why do we need to make a Double function? Can't we prove like this: Let's say the Turing machine < EvalS | Clean > has $n_0$ states. Let $\textrm{BadS}$ denote < Create_n0 | EvalS | Clean >. $\mathrm{BadS}$ has $n_0$ states but has more than $S(n_0)$ shifts, therefore, contradiction.

Answer 1

How do you know that $ M' = \langle Create_{n0} \mid Double \mid EvalS \mid Clean \rangle$ has N states?

By definition $n_0$ is the size of the machine $M = \langle Double \mid EvalS \mid Clean \rangle$; in order to build $M'$ you add $Create_{n_0}$ but in orther to do this you simply need $n_0$ more states: on state $s_1$ write 1, move right and go to $s_2$; then write 1, move right and go to $s_3$, and so on. After writing $n_0$ $1s$, $M'$ enters the state $s_{n_0+1}$ which is simply the initial state of $M$ (states $s_{n_0+1},...,s_{2n_0}$ of $M'$ are a copy of the states of $M$).

Why do we need to make "Double" function? Can't we prove like this : Let's say turing machine $M = \langle EvalS \mid Clean \rangle$ has $n_0$ states. Let $BadS$ denote $\langle Create_{n_0} \mid EvalS \mid Clean \rangle$. $BadS$ has $n_0$ states but have more than $S(n_0)$ shifts, therefore, contradiction.

No you cannot because in this case $BadS$ has more than $n_0$ states: $|BadS| > |M| = n_0$

A note: though the proof of undecidability of $S(n)$ using the undecidability of the halting problem of a Turing machine on a blank tape is easier, the first proof written in Wikipedia (that you reference in your question) is more interesting because it only uses a "self-reference" of $S(n)$ to itself in order to derive a contradiction.

Answer 2

Here's a simple proof of the non-computability of the Busy Beaver function:

Assume BB is computable. Then we can build a program that accepts a TM specification M and input x. Compute n = BB(|M|), where |M| is the number of states of TM M. Next, simulate M(x) for n time-steps. If M(x) halts, accept. If after n time-steps M(x) has not halted, reject. This program solves the Halting-Problem, a contradiction - QED.