2
$\begingroup$

I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold.

(BB(n) is defined as the number of steps made by n-state Busy Beavers.)

Theorem: BB(n) is uncomputable. That is, there is no Turing machine that can take as input n and computes BB(n).


Proof: Suppose to the contrary that such a machine existed, and call it T. We will use T to construct a machine which solves the halting problem as follows:

On input < T, w >, a description of a Turing machine and its associated input, we can determine in finite time the number of states that T has (it is encoded in the description of T).

Now simply compute BB(n), where n is the number of states in T, and simulate T on input w, counting its steps as it proceeds. Eventually the simulation of T either halts, or makes more steps than BB(n).

In the former case, we may stop the computation and declare that T halts. In the latter, we know that BB(n) is the maximal number of steps that can occur for any Turing machine with n states that eventually halts. Therefore, if T had not halted on the input w, it must never halt.

We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.

This is a contradiction, so the sequence BB(n) cannot be computable.

If we assume that T can calculate BB(n) for any n, don't we also have to assume that it does halt, and therefore that it will not exceed the steps of BB(n)? (That would also mean that using T to solve the halting problem does not work)

$\endgroup$
  • 1
    $\begingroup$ "... call it T. We will use T to ... as follows: ​ On input < T, w >, a ..." ​ ​ ​ This is a problem. ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Feb 10 '16 at 23:09
  • $\begingroup$ I just copy pasted the proof. Are you saying that the author actually meant that another Turing Machine "T" was fed into the halting-problem solver, not the T that can calculate BB(n)? $\endgroup$ – x squared Feb 10 '16 at 23:19
2
$\begingroup$

Just for the completeness, I will present my proof that shows uncomputability of BB function. The structure of a correct proof would look something like the following.

  1. Construct a universal Turing machine U that simulates any other Turing machines but writes ‘1’ on the output tape for every step of the simulation.

  2. For any Turing machine M, there is an encoding 〈M〉for U. We create a new Turing machine by adding new states in U which first writes〈M〉on its input tape and runs it on U. Call this new Turing machine UM.

  3. Let n be the number of states in UM, and m be the number of states in M. We can see that BB(n) upper-bounds the number of 1’s outputted by UM and also upper-bounds the maximal number of steps run by the halting Turing machine with m states. Hence, S(m) <= BB(n), where S(m) is the maximal number of steps run by a halting Turing machine with m states.

  4. Given a Turing machine of size m, we can always determine corresponding value for n.

  5. If there is any function that always upper bounds S, it is uncomputable as it will contradict with the result from the halting problem. (Run a Turing machine that many steps to determine whether it halts or not)

$\endgroup$
1
$\begingroup$

This can't be right. E.g. I can build a 2-state Turing machine, which takes an input $\omega$ and just moves right and halts after overwriting the first blank with a $1$. If $\omega$ is long enough (longer than $\mathop{BB}(2)$ in our case), my TM will take more than $\mathop{BB}(2)$ steps and halt. Besides, $\mathop{B}$ is defined as writing on an initially blank tape, and is the number of $1$ written, not the number of steps.

$\endgroup$
  • 1
    $\begingroup$ As described here "actually, Rado asked mainly about the maximum number of symbols any machine can write on the tape before halting. But the maximum number of steps, which Rado called S(n), has the same basic properties and is easier to reason about.", or here "Alternatively, some authors define a busy beaver as a Turing machine that performs a maximum number S(n) of steps when started on an initially blank tape before halting (Wolfram 2002, p. 889)" $\endgroup$ – x squared Feb 13 '16 at 9:43
  • $\begingroup$ That said, I think your counter argument against this proof is valid. But as far as I understand the matter (which doesn't mean much), the whole $BB$ problem talks only about Turing Machines whose memory tapes are zero-initialized. So when disallowing input parameters, the proof should be correct, right? $\endgroup$ – x squared Feb 13 '16 at 9:53
0
$\begingroup$

EDIT: The proof seems to contain two errors:

  1. The proof uses the same T to denote the Turing Machine that can solve BB(n) as well as for the input-TM for the halting-problem solver. So we have to rename the input-TM.

  2. From http://mathworld.wolfram.com/BusyBeaver.html:

    [...] some authors define a busy beaver as a Turing machine that performs a maximum number S(n) of steps when started on an initially blank tape before halting

    This proof obviously uses above definition which states that Busy Beavers do more steps than any Turing Machine with zero-initialized tape. That means, we can only test the halting-problem on Turing Machines with no input parameters. So we have to remove $\omega$ as input parameter.


The correct formulation would then be:

Theorem: BB(n) is uncomputable. That is, there is no Turing machine that can take as input n and computes BB(n).

Proof: Suppose to the contrary that such a machine existed, and call it T. We will use T to construct a machine which solves the halting problem as follows:

On input < TM >, a description of a Turing machine and its associated input, we can determine in finite time the number of states that TM has (it is encoded in the description of TM).

Now simply use T to compute BB(n), where n is the number of states in TM, and simulate TM, counting its steps as it proceeds. Eventually the simulation of TM either halts, or makes more steps than BB(n).

In the former case, we may stop the computation and declare that TM halts. In the latter, we know that BB(n) is the maximal number of steps that can occur for any Turing machine with n states that eventually halts. Therefore, if TM had not halted on the input w, it must never halt.

We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.

This is a contradiction, so the sequence BB(n) cannot be computable.

Or as pseudocde:

T(n):
    return BB(n)

halting_problem_solver(TM):
    n := number of states in TM
    BB_n := T(n)
    steps := 0
    in each step of TM() simulation:
        steps = steps + 1
        if steps > BB_n:
            return T will not halt!
    return T halts
$\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.