[Solved]: Understanding proof for Busy Beaver being uncomputable

Problem Detail: 

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)

Asked By : x squared

Answered By : x squared

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 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52949