40
$\begingroup$

Context: I just completed the first quarter of an Intro to Real Analysis class, and while I was thinking about how some functions (like $x^2$) aren't uniformly continuous because they, roughly speaking, "increase too quickly" (I'm aware of the actual $\varepsilon$-$\delta$ definition), I wondered if there was a "fastest increasing" function as its input goes to infinity (discrete or continuous, it doesn't really matter).

My Research: After a moment of thought, I realized there wasn't one, since we could merely compose it with itself or square it or tack a factorial on the end or do any number of other things. But I was still curious, so I took to the internet and was able to find things like the Ackerman Function and the Fast-growing Hierarchy on Wikipedia. These functions are cool and all, but, as far as I can tell, they don't serve a purpose other than being functions that increase really quickly. So this led to my question...

Question: What is the fastest increasing function that's useful in some area of math? By "useful" I mean something similar to how Graham's Number was used in a proof in a non-arbitrary way. I'm wondering about functions that grow incredibly quickly and exist for reasons other than that they grow incredibly quickly.

Based on my research, it looks some kind of computer science comes into play with these functions, and so do large ordinals. I don't know a lot about these areas because I'm just a second year right now, so don't assume too much background knowledge please.

$\endgroup$
  • 9
    $\begingroup$ Incidentally, Ackermann's function does appear naturally as the running time of certain algorithms; the running time of the important union-find algorithm is the inverse of the Ackermann function. Ackermann-like functions also appear naturally in the proofs of several theorems of Ramsey theory; van der Waerden's theorem is a well-known example. $\endgroup$ – MJD Dec 17 '14 at 6:45
  • 4
    $\begingroup$ I looked into Graham's number recently, and it turns out not to have ever been used in any proof, and in particular it does not appear in the paper that it is claimed to have appeared in. The bound given there is vastly smaller, and also Ackermann-like. $\endgroup$ – MJD Dec 17 '14 at 6:50
  • 1
    $\begingroup$ Your linked Wikipedia article actually states a purpose for the Ackerman function. $\endgroup$ – Harald Dec 17 '14 at 14:12
40
$\begingroup$

The busy beaver function $BB(n)$ is (informally) an upper bound on the amount of time a computer of size $n$ can compute without going into an infinite loop. It increases much more quickly than does Ackermann's function; so much so that it can't be computed at all. In fact, it increases more quickly than any function that can be computed.

The busy beaver function shows up in all sorts of examples of non-computability. For example, Are there any examples of non-computable real numbers? asked for an example of a real number that can't be computed by any process, and among the answers was $$\sum_{i=1}^\infty 2^{-BB(i)}=2^{-1}+2^{-6}+2^{-21}+2^{-107}+\ ... \ \approx 0.515625476837158203125000000000006$$ in which the busy beaver function plays a central role.

$\endgroup$
  • 2
    $\begingroup$ See also this blog article about BB. $\endgroup$ – Clement C. Dec 17 '14 at 6:44
  • 5
    $\begingroup$ Here is another related blog article I enjoyed, "Who Can Name the Bigger Number?" $\endgroup$ – MJD Dec 17 '14 at 6:57
  • $\begingroup$ @MJD The blog article is a perfect thing for a lecture to high school students! I really love the game that is presented there at the beginning :) (btw, (x->9^(9^x))^(9^(9^9)) (9) would be my try :) ) $\endgroup$ – yo' Dec 18 '14 at 0:10
4
$\begingroup$

You mentioned the fast growing hierarchy (FGH), but then dropped it, deeming it useful only for the purposes of the fact that it grows fast. But to a googologist, the fast growing hierarchy is something more. (ok, so a googologist studies large numbers, but still!)

One of the most fundamental things about FGH is that it's well suited for induction and able to grow fast. This allows it to be a compact way to approximate large things and compare them. For example, it can be seen that

$$\underbrace{f_\omega(2+n)>2+3\uparrow^n3}_{\text{easily proven}}$$

$$\begin{align}f_{\omega+1}(64)&=\underbrace{f_\omega(f_\omega(\dots f_\omega(64)\dots))}_{64}\\&>\underbrace{f_\omega(f_\omega(\dots f_\omega(2+4)\dots))}_{64}\\&>\underbrace{f_\omega(f_\omega(\dots f_\omega(2+3\uparrow^43)\dots))}_{63}\\&>\underbrace{f_\omega(f_\omega(\dots f_\omega(2+3\uparrow^{3\uparrow^43}3)\dots))}_{62}\\&>\dots\\&>2+\text{Graham's number}\end{align}$$

Likewise, it is showable that $f_{\omega+1}(63)$ is less than Graham's number. To a googologist, this function is great, as it now gives you a manageable form of Graham's number to compare to other large numbers.


Another famous example of FGH is its relation to the Goodstein sequence and that the Goodstein sequence cannot be proven to terminate in Peano arithmetic.

The FGH is stronger, and likewise, it can be proven that any function on the order of $f_{\epsilon_0}(n)$ and higher cannot be proven to terminate in Peano arithmetic, where

$$\epsilon_0=\sup\{\omega,\omega^\omega,\omega^{\omega^\omega}\dots\}$$

which is probably not only simpler to understand and straight forward than the Goodstein sequence, but a generalization.


The last little point I will make is that FGH can grow as fast as any computable function. This means that we can approximate things like $\operatorname{TREE}(3)$!

$$\operatorname{TREE}(n)\approx f_{\theta(\Omega^\omega\omega,0)}(n)$$

as explained in this answer.


So argue it one way or another, the fast growing hierarchy is indeed useful for more than just growing fast, though maybe not much useful for things outside the realm of large numbers.

$\endgroup$
2
$\begingroup$

On a different matter -- it does not (even remotely) grow as fast as the Busy-Beaver function, but there exist results saying that a general family of properties of graphs can be $\varepsilon$-tested in $\phi(\varepsilon)$ queries to the graph [GGR98], where $\phi(\varepsilon)$ is of the form $$2^{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}$$ where the dots hide a tower of $1/\varepsilon^5$ $2$'s. (See e.g. these lecture notes.)

Furthermore, it can also be shown that a tower of $2$'s of height at least $\log^2(1/\varepsilon)$ is necessary in the query complexity (see this).

$\endgroup$
  • 3
    $\begingroup$ Tetration $\endgroup$ – smci Dec 17 '14 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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