BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running it for BB(n) steps.

So given some n-state TM, can we construct an m-state TM, where m>n, to calculate BB(n) and thus decides if it halts?

Now some might say that this is equivalent to solving the halting problem, but I don't think so. Because given an arbitrary TM, we don't in fact know how many states it has. And if we don't know n, we certainly can't find m.

If the answer is in the negative, then how is it that we can in fact find out the values of BB(n) for small n? What's the connection between incomputability and unknowability?

  • 2
    $\begingroup$ The halting problem implies that there can be no computable bound for the busy beaver function $BB(n)$. Otherwise, as you suggest, one could use the bound to solve the halting problem. Moreover, the halting problem also implies that there can be no computable bound $m = m(n)$ on the smallest number of states in a TM that can decide whether every $n$-state TM halts. This doesn't rule out clever ad-hoc proofs that $BB(n)$ or $m(n)$ are at most some value for particular $n$. $\endgroup$ – András Salamon May 25 '13 at 9:30

For a particular $n$, there are at most $2^{O(n)}$ different TMs with $n$ states, and we can have a list for all of them: 1 is the TM halts, and 0 otherwise. A TM that has this "list" in its memory can decide the problem you give in your question. Not only this language is decidable - it is even regular!

The "halting problem" states though, that there is no TM that works for all possible $n$'s.

  • $\begingroup$ +1 Nice. Note that Ran G. gives the limit based on isomorphism up to renaming of the states and symbols; clearly there are infinitely many TMs if you distinguish between TMs whose states and symbols are called different things. $\endgroup$ – Patrick87 May 28 '13 at 20:54
  • 1
    $\begingroup$ It should be emphasized that Ran's answer is nonuniform, i.e., there is no procedure which takes $n$ and gives the magic list. In fact, given any axiom system for mathematics, there will be an $n$ for which that axiom system cannot construct and prove that it got the correct list. $\endgroup$ – Andrej Bauer May 29 '13 at 5:00

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.