# Fast-growing hierarchy and Turing machines

Is it possible to get an estimate of the size of a Turing machine computing $f_\alpha(n)$, for a given $\alpha$ (I am especialy interested in moderately large $\alpha$ like the ordinal of Fefferman-Schütte, or the small Veblen ordinal)? The idea is to get an idea of the size of the BusyBeaver function $BB(n)$ for moderate values of $n$, as the litterature usually only mention the exact known values (for $n\le 6$) and the fact that such values will probably never be known for $n=10$, say.

• A reminder of the meaning of $f_\alpha$ in this context would be welcome. Commented Aug 2, 2012 at 12:24
• @Lee: The fast-growing functions are defined on wikipedia - en.wikipedia.org/wiki/Fast-growing_hierarchy - note the dependency on the choice of ordinal notations. Commented Aug 2, 2012 at 15:22
• I am not sure what you mean by BB(15) uncomputable (it would imply that the Halting problem could not be solved for some 15-states (and 2 symbols) machines, no?) But this obviously does not mean that BB(15) is "incomprehensibly large", to quote Friedman : it could well be that actually BB(15) is smaller than Graham number, say, but simply we will never be able to prove it... So what I am trying to do is to prove, for instance, that BB(15) is greater than $f_{\epsilon_0}(15)$ (which is already quite large, if ridiculously smaller than TREE (3)), just by constructing a suitable Turing machine.. Commented Aug 2, 2012 at 20:21
• @Steve, theoretically BB(15) is computable, it is just a finite number. I guess you mean uncomputable in practice. Commented Aug 3, 2012 at 0:33
• If α was a recursive ordinal we could use K(α)+c as an upper-bound. I don't know what can be said when α is not recursive, can we even find an algorithm to compute it or is its existence a non-constructive (which might mean that we cannot give any number as an upper-bound)? Commented Aug 3, 2012 at 0:40

## 1 Answer

Consider Gödel's speed-up theorem which discusses sentences like "this sentence is unprovable in theory T with less than $$\phi$$ symbols" where $$\phi$$ is some computable formula like TREE(3), and T is some consistent, effective theory like PA or ZFC with large cardinals (assuming those are consistent). Call the above sentence S.

Per the speed-up theorem, S is both true and provable (see the wiki article). The provability means that for reasonable theories, there is a relatively small $$n$$ such that an $$n$$-state Turing machine will eventually (by unbounded search) find the proof and halt, but that the running time will be (much) longer than $$\phi$$. Of course BB(n) has to be even bigger than that. With a suitable encoding, n=15 might be enough. So BB(n) quickly dominates any computable formula that can be written down.

"BB(15) is uncomputable" could be interpreted something like: there is a 15-state TM that halts if and only if your favorite strong arithmetic theory T is inconsistent. So if you believe that T really is consistent, that means you'll never be able to know what BB(15) is.