Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

What grows faster: Busy Beaver function, TREE function or BEAF largest resursive functions (legions, lugions, lagions...)?

share|cite|improve this question

closed as off topic by Bugs Bunny, Gjergji Zaimi, Dan Petersen, David Roberts, Bill Johnson Sep 14 '12 at 10:40

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer 1

Much too easy for this site, and already answered. Anyway, BusyBeaver grows faster that any computable function (almost by definition); as the other two are computable... (btw, TREE grows inimaginably faster that the recursive functions you cite next). All these questions tend to show that you have not studied the>fast-growing hierarchy : in this notation, Conway's $n\rightarrow n \rightarrow\dots\rightarrow n$ (with $n$ arrows) is (much) smaller than $f_{\omega^2+1}(n)$, and any "recursive" construction in the line of BEAF grows slower than $f_{\omega^\omega}$, while TREE grows much faster than $f_{\epsilon_0}$, or even $f_{\Gamma_0}$...

share|cite|improve this answer
For now, I studied FGH and figured out that TREE(n) surpasses <math>f_{\vartheta(\Omega^\omega)}(n)</math>. –  Ikosarakt May 15 '13 at 23:02

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