Aside from the power, gamma, exponential functions are there any other very fast growing functions in (semi-) regular use?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
It depends on what you mean by "in use"; the Busy Beaver function, which grows strictly faster than any sequence produceable by a Turing machine, is sometimes used in theoretical results in computability although only the first four terms are actually known. I'm not sure if it's the sort of thing you're looking for. |
|||||
|
|
Tetration is a standard example. Consider, for example, $f(n) = 2\uparrow\uparrow n$, so f(1) = 2, f(2) = $2^2$, f(3) = $2^{2^2}$, f(4) = $2^{2^{2^2}}$, etc. |
|||||
|
|
An upper bound in Szemerédi's regularity lemma grows pretty fast: it is "given by a $\log(1/\epsilon^5)$-level iterated exponential of $m$", and there's a lower bound by Gowers which is "a $\log(1/\epsilon)$-level iterated exponential of $m$". Less spectacular is the upper bound in Szemerédi's theorem: $2^{2^{\delta^{-2^{2^{k+9}}}}}$. |
|||
|
|
