# Uncomputability of Busy Beaver Function

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.

• Could you include the relevant parts of the proof in your question? At the moment, your question doesn't make any sense without cross-referencing with the Wikipedia page. Thanks! Commented May 18, 2017 at 16:19

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.

• Could you give one more detailed explanation why "$BadS$ has more than $n_0$ states"? Do you mean that the composition $X \mid EvalS$ where $X$ can be $Create_{n0}$ or $Double$ must add states based on the sum of the state number of $X,EvalS$ (if so could you show why it is that case)? Commented Mar 10 at 7:38
• More specifically, to ensure "$M'$ enters the state $s_{n_0+1}$ which is simply the initial state of $M$", maybe we should have $(s_i,0,s_{i+1},1,L),1\le i\le n_0-1$. Then we have $(s_{n_0},0,s_{n_0+1},1,N)$ or $(s_{n_0},0,s_{n_0+1},1,L),(s_{n_0+1},0,s_{n_0+1},0,R)$ to ensure we start at the start cell (Here I assume the cell with the leftmost nonblank symbol is the start cell). Commented Mar 10 at 11:26

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.

• This seems incorrect - BB(|M|) is the maximum number of steps which the machine can take on the empty input (or input just consisting of 0s, etc). We've no guarantee of the number of steps which a machine with |M| states might take on arbitrary inputs. Eg: a machine reads 1s to the right until it can't any longer. This machine runs for a number of steps which is a function of the size of the input.
– seth
Commented May 19, 2023 at 21:55
• @seth Do you mean the author description "input $x$" should be "a blank (all-0) tape" as the definition en.wikipedia.org/wiki/Busy_beaver#The_game says? If so I agree with you because $BB(|M|)$ only ensures the maximal steps when having the empty input. Commented Mar 10 at 8:38
• If $x$ is the empty string, then this is same as this QA Commented Mar 10 at 11:04
• I'm not sure I agree with my comment any more. The halting problem reduces to the halting problem on a blank tape: create a new TM which first writes your input to the blank tape, then simulates the original TM. I think that the answer is just a little incomplete in that the machine specified isn't a decider for the "standard" halting problem.
– seth
Commented Mar 11 at 11:59