Take the 2-minute tour ×
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.

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?

share|improve this question
    
Here is a question you might want to see. –  J. M. Nov 29 '11 at 6:41
2  
Your question is not well posed, given a function you can always produce one that is a lot faster growing while staying within a "few lines". –  Listing Nov 29 '11 at 7:50
2  
"Take the best answer in this thread and add a factorial at the end"... Is this a good description? :) –  N. S. Dec 19 '11 at 0:26

5 Answers 5

up vote 6 down vote accepted

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)$, $l(w) \ge l(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.

share|improve this answer
    
I hope you don't mind that I edited your math expressions into MathJaX format and added a couple of WP links. I tried to get everything right, but please check. –  r.e.s. Dec 19 '11 at 14:05
    
Thank you very much, r.e.s.! Just found a few errors, which I will correct. –  Deedlit Dec 22 '11 at 7:22

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.

share|improve this answer
    
The fast-growing hierarchy article at WP might also be of interest. –  r.e.s. Nov 29 '11 at 18:34
4  
@r.e.s. Yes, thanks. Wikipedia didn't exist when I originally wrote the above. But it's growing fast. –  Bill Dubuque Nov 29 '11 at 19:29
4  
Another expository article to add to the list Who Can Name the Bigger Number? by Scott Aaronson –  user18325 Dec 19 '11 at 4:40

I do not know wether 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.

share|improve this answer
6  
$A(A(n,n),A(n,n))$ is probably faster growing ;) –  Listing Nov 29 '11 at 7:43
2  
@Listing: Have you considered $A(A(A(n,n),A(n,n)),A(A(n,n),A(n,n)))$? –  Isaac Solomon Dec 19 '11 at 4:44
    
All you need to do is pass it Graham's number in both arguments. –  Cole Johnson Feb 7 at 2:21
    
@ColeJohnson: But then the function would be constant. –  Raphael Feb 7 at 7:24

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.

share|improve this answer

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}.

share|improve this answer

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.