3
$\begingroup$

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 "Double" function? Can't we prove like this : Let's say turing machine < EvalS | Clean > has n0 states. Let BadS denote < Create_n0 | EvalS | Clean >. BadS has n0 states but have more than S(n0) shifts, therefore, contradiction.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – David Richerby May 18 '17 at 16:19
3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\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.