# Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?

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?

• 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$. – 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.
• 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. – Andrej Bauer May 29 '13 at 5:00