What is the fastest growing total computable function you can describe in a few lines?

Question

What is the fastest growing total computable function you can describe in a few lines? Well, not necessarily the fastest - I just would like to know how far an ingenious mathematician can go using only a few lines, and what systematic approaches exist for this purpose.

How farther you can go if we the restriction of computability is lifted?

Answer 1

For a nice fast-growing function, consider the following:

Given rooted trees $S$ and $T$ whose vertices are labeled from $\{1,2,\cdots,k\}$, define a gap embedding as a label preserving embedding $h$ from $S$ into $T$ that satisfies the following: given $u$, $v$ vertices of $S$ such that $v$ is the child of $u$. For any vertex $w$ of $T$ that lies in between $h(u)$ and $h(v)$, $label(w) \ge label(h(v))$.

Given this definition, define $ETree(k)$ to be the longest sequence $T_i$ of rooted trees labeled from $\{1,2,\cdots,k\}$ such that $T_i$ has no more than $i$ vertices, and for no $i < j$ is there a gap embedding from $T_i$ into $T_j$.

The above construction is due to Harvey Friedman. He showed that no such sequence could be infinite (i.e. that rooted labeled trees are well-quasi-ordered under gap embedding), and it follows from Koenig's Tree Lemma that there is a longest such sequence.

The function $ETree(k)$ grows extremely fast. It grows at the rate of $F_{\psi_{\Omega_1} (\Omega_\omega)} (k)$. (Look up the fast-growing hierarchy.)

One can also get extremely fast growing functions using ordinal hierarchies. Let $I(a)$ be the $a$'th weakly inacessible cardinal. Consider the following: (here $a,b,c,d,e$ are ordinals, $\phi$ is the Veblen function, $C_n(a,b)$ are sets of ordinals, $\psi$ and $f$ are functions on ordinals.)

$C_0(a,b) = b \cup {0}$

$C_{n+1}(a,b) = \{c+d, \phi(c,d), \aleph_c, I(c), \psi(e,d), f(e,c,d) | c,d,e \in C_n(a,b), e < a\}$

$C(a,b) = \cup C_n(a,b)$

$f(a,n,b) =$ largest finite ordinal in $C_n(a,b)$

$\psi(a,b) = b$'th ordinal such that $b \notin C(a,b)$

Then, for example, $f(I(I(I(I(0)))),x,x)$ is an extremely fast growing function, much faster than $ETree$. To help understand this construction, see "Ordinal collapsing function" on wikipedia. If that is still confusing, look at

http://math.ucr.edu/home/baez/week236.html

for an introduction to ordinals, and

http://groups.google.com/group/sci.math/browse_thread/thread/b4b2769c6359b3e9/5317b10cbf60196

for a description of how ordinals can be used to define large numbers.

EDIT: Perhaps some more explanation is needed. $C(a,b)$ is the smallest set of ordinals containing all ordinals less than $b$ and $0$ and closed under the operations listed in the second line. The definition may appear circular, but it is well-defined by induction on $a$; given $f(c,n,b)$ and $\psi(c,b)$ for $c < a$, we define $C_n(a,b)$, and given $C_n(a,b)$, we define $f(a,n,b)$ and $\psi(a,b)$.

Some analysis of $f(a,n,b)$:

$f(0,0,b)$ is the largest finite ordinal in $C_0(0,b) = b$, which is $b-1$.

$f(0,1,b)$ is $2(b-1)$ if $b \ge 2$, otherwise it is $\phi(0,0) = 1$.

$f(0,n,b)$ is $2^{b-1}$ if $b \ge 2$, otherwise it is $2^{n-1}$

$f(1,0,b)$ is again $b-1$ if $b \ge 1$, $0$ if $b = 0$

$f(1,1,b)$ is $2^{b-1} (b-1)$ if $b \ge 2$ otherwise it is $1$

$f(1,n,b) > Tower_n (b-1) > 2\uparrow\uparrow n$ for $b \ge 2$

$f(2,n,b) > 2\uparrow\uparrow\uparrow n$ for $b \ge 2$

$f(m,n,b) > 2 \uparrow^{m+1} n$ for $b \ge 2$

$f(\omega,0,b) = b-1$ for $b \ge 2$

$f(\omega,1,b) = f(b-1,b-1,b-1) \ge 2 \uparrow^{b}(b-1)$ for $b \ge 2$

$f(\omega,2,b) = f(f(\omega,1,b),f(\omega,1,b),f(\omega,1,b)) \ge 2 \uparrow^{2 \uparrow^b (b-1)}(2 \uparrow^b (b-1))$

$f(\omega,n,b)$ is the function $f(x,x,x)$ applied $n$ times starting from $b-1$, which is greater than $F_{\omega+1}(n)$ where $F$ is the fast-growing hierarchy.

$F(\omega+1,n,b)$ is the function $f(\omega,x,x)$ applied $n$ times starting from $b-1$, which is greater than $F_{\omega+2}(n)$.

Each time we add $1$ to $a$, we go to a function which iterates the previous one $n$ times; each time we increase a to a limit ordinal, we diagonalize over previous functions. So the task becomes defining very large countable ordinals.

Answer 2

I do not know whether it is the fastest, but historically the Ackermann function was the first (afaik):

$\qquad A(m, n) =\begin{cases}n+1 & \mbox{if } m = 0 \\A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0.\end{cases}$

It generalises the idea that $+$, $\cdot$, $\exp$ and so on form a natural series of operators; $A$ excedes them all by controlling the stacking level in the second parameter.

It has been proven that $A$ (or rather $A(n,n)$) is not primitive recursive by showing that it grows faster than any primitive recursive function, including all exponential functions.

Answer 3

Most fast-growing functions are constructed by a recursive scheme analogous to the well-known Ackermann function - namely one repeatedly iterates a function and then diagonalizes. Thus iterating addition yields multiplication, which iterated yields exponentiation, which iterated yields tetration, etc. Diagonalizing the resulting sequence of functions yields a faster-growing Ackermann function - which itself may be successively iterated, diagonalized, etc. Paul du Bois-Reymond discovered such diagonalization on growth rates of functions ("orders of infinity") in 1875, long before Cantor's better-known rediscovery (1891), employed to show $|2^S| > |S|$.

Proof-theorists use analogous recursive schemes to construct notation systems for ordinals - which they employ to measure the strength of logical systems. Functions and numbers notated by such means (whether finite or infinite) tremendously dwarf those that occur in most all other branches of mathematics. Thus I highly recommend that you consult the literature on ordinal notation systems.

Below are some expository references on related topics (from an old sci.math post).

[Ruc] Rucker, Rudy. Infinity and The Mind, 1995, 342 pp. Princeton U. Pr.

[Spe] Spencer, Joel. Large numbers and unprovable theorems, Amer. Math. Monthly, Dec 1983, 669-675.

[Smo] Smorynski, Craig (all three papers are reprinted in [HFR])
Some rapidly growing functions, Math. Intelligencer, 2 1980, 149-154.
The Varieties of Arboreal Experience, Math. Intelligencer, 4 1982, 182-188.
"Big" News from Archimedes to Friedman, Notices Amer. Math. Soc. 30 1983, 251-256.

[Kol] Kolata, Gina. Does Godel's theorem matter to mathematics? Science 218 11/19/1982, 779-780; reprinted in [HFR]

[Sim] Simpson, Stephen G. Unprovable theorems and fast-growing functions, Contemp. Math. 65 1987, 359-394.

[HFR] Harrington, L.A. et.al. (editors) Harvey Friedman's Research on the Foundations of Mathematics, Elsevier 1985.

Answer 4

An example which grows faster than any computable function (for obvious reasons): Let BB(n) denote the time it takes for the longest halting Turing machine with n symbols to halt.

edit perhaps "obvious" was an exaggeration: Was BB computable then you could write a program to check whether any input program halts or not by seeing if it stops before BB(length(program)) steps, but this is not computable by Turing's argument so BB is not computable. Also let f be any computable function, then you can see that BB grows faster than f, since there is a program that takes f steps to halt.

Answer 5

Well, for example:

Rule 1 (only 2 entries):

{a,b} = a^b

Rule 2 (2nd entry is 1):

{a,1 #} = a

Rule 3 (last entry is 1):

{#,1} = {#}

Rule 4 (string of 1's from the 3rd entry to nth):

{a,b,1,1,...,1,1,c #} = {a,a,a,a,...,a,{a,b-1,1,1,...,1,1,c #},c-1 #}

Rule 5 (otherwise):

{a,b,c #} = {a,{a,b-1,c #},c-1 #}

Here # denotes the unchanged remainder of array. Then my function is f(n) = {n,n,n,...,n,n,n}.