Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
A reminder of the meaning of $f_\alpha$ in this context would be welcome. –  Lee Mosher Aug 2 '12 at 12:24
    
I believe $BB(15)$ is known to be uncomputable: en.wikipedia.org/wiki/… --so by moderate, I assume you mean $7 \le n \le 14$, no? –  Steve Huntsman Aug 2 '12 at 12:26
1  
@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. –  François G. Dorais Aug 2 '12 at 15:22
3  
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.. –  Feldmann Denis Aug 2 '12 at 20:21
    
@Steve, theoretically BB(15) is computable, it is just a finite number. I guess you mean uncomputable in practice. –  Kaveh Aug 3 '12 at 0:33
show 6 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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