4
$\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$
2
  • 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, 2016 at 23:09
  • 1
    $\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, 2016 at 23:19

4 Answers 4

4
$\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$
1
  • $\begingroup$ Your pseudocode is very clear and helpful. It summarises the proof. $\endgroup$
    – An5Drama
    Mar 10 at 9:35
4
$\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$
3
  • 1
    $\begingroup$ More specifically, 1. "there is an encoding $\langle M\rangle$ for $U$" means $U$ takes one Turing machine $\langle M\rangle$ as the input. It corresponds to the above corrected reference link "When $ M$ is given the input $ \left \langle T \right \rangle$". $\endgroup$
    – An5Drama
    Mar 10 at 9:47
  • 1
    $\begingroup$ 2. "also upper-bounds the maximal number of steps run by the halting Turing machine with m states" because we runs $M$ on $U$ so the steps of $M$ is included in $UM$. (IMHO $M$ can be any machine as what the halting problem assumes.) 3. $BB(n)$ is same as $S(n)$. 4. "we can always determine corresponding value for n.": $n$ depends on how we "Construct a universal Turing machine U". $\endgroup$
    – An5Drama
    Mar 10 at 9:59
  • 1
    $\begingroup$ 5. "If there is any function that always upper bounds S" This ensures we can find one TM runs more steps than $M$. So we can "Run a Turing machine that many steps to determine whether it halts or not", i.e. $BB(n)\ge S(m)$ steps (This is same as halting_problem_solver(TM) in the OP's answer). Please point out errors if any. Thanks in advance. $\endgroup$
    – An5Drama
    Mar 10 at 10:01
3
$\begingroup$

The reference blog has changed and it seems to have been corrected which includes the OP's correction. Although the waybackmachine archived this blog old uncorrected version (2013 version) but it can't render the formula images.

The corrected reference blog (it is similar to this lecture p9):

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

Proof. Suppose to the contrary that such a machine existed, and call it $ A$. We will use $ A$ to construct another machine, say $ M$ which solves the halting problem as follows. We will use the version of the halting problem where the input is assumed to be the empty string (i.e., there is no input); this problem is also undecidable.

When $ M$ is given the input $ \left \langle T \right \rangle$, a description of a Turing machine, $ M$ determines in finite time the number of states that $ T$ has (it is encoded in the description of $ T$), and then uses $ A$ to compute $ BB(n)$, where $ n$ is the number of states in $ T$. The machine $ M$ then simulates $ T$ on the empty string input, counting its steps as it proceeds. Eventually the simulation of $ T$ either halts, or makes more steps than $ BB(n)$. In the former case, $ M$ 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, 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.

Here I give one summary for the corrected one with some more description of the implementation of $M$:

  1. We will use the version of the halting problem where the input is assumed to be the empty string (i.e., there is no input); this problem is also undecidable.

    See this QA whose main idea is reduction from one specific problem to one specific problem where one of the 2 problems is already investigated.

  2. $ M$ determines in finite time the number of states that $ T$ has (it is encoded in the description of $ T$)

    See this QA. The ending form of the tape depends on the implementation of $A$. Maybe we writes $n$ 1s on the tape and $A$ reads these specific number of 1s to compute $BB(n)$. (Anyone knowing one specific TM to compute the cardinality of a set can help improve this answer. Thanks in advance.)

  3. and then uses $ A$ to compute $ BB(n)$

    Here $A$ is implemented implicitly inside $M$ like how we implement composition of multiple Turing Machines.

  4. The machine $ M$ then simulates $ T$ on the empty string input Since we may probably prints $BB(n)$ 1s on the tape, to ensure the empty string input and also remembering $BB(n)$, we can use the Multitape Turing machine.

    More specifically, assume we have $$ \begin{align*} 0: &\overbrace{11\cdots11}^{BB(n)\text{ times}}q_{k}\\ 1: &00\cdots00\cdots \end{align*} $$ Then we may proceed until $$ \begin{align*} 0: &&q_{k'}&00\cdots00\cdots\\ 1: &&\cdots00&\overbrace{11\cdots11}^{BB(n)\text{ times}}00\cdots \end{align*} $$ Then we use tape-0 to simulate $T$. Meanwhile, we change 1 to 0 of the tape-1 for

    counting its steps as it proceeds

    and compare the step number with $BB(n)$ where we may end up as the following when simulating $T$ (The detailed values of $10\cdots 010$ depends on the behavior of $T$): $$ \begin{align*} 0: &&10\cdots 010&q_{k''}\cdots\\ 1: &&\overbrace{00\cdots00}^{BB(n)\text{ times}}1&0\cdots \end{align*} $$ Here we use $q_{k''}$ to mean that $T$ won't halt by (more specifically, $T$ is one 2-symbol n-state Turing machine)

    $ BB(n)$ is the maximal number of steps that can occur for any Turing machine with $ n$ states that eventually halts.

    (Here I didn't give the behavior of the tape-1 before "The machine $ M$ then simulates $ T$". But we can probably use many states to ensure the tape-1 keeps all 0s before we doing the above process.)

  5. proclaim an infinite loop

    i.e. non-halt.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks so much for investigating the matter and for sharing your insights. I wasn't even aware that the blog has been updated! $\endgroup$
    – x squared
    Mar 10 at 19:51
2
$\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$
3
  • 3
    $\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, 2016 at 9:43
  • 2
    $\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, 2016 at 9:53
  • 1
    $\begingroup$ This answer implements one TM similar to this general one which is same as the 3rd paragraph of the wikipedia related contents. $\endgroup$
    – An5Drama
    Mar 10 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.