20
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Here is a question you might want to see. $\endgroup$ – J. M. is a poor mathematician Nov 29 '11 at 6:41
  • 3
    $\begingroup$ 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". $\endgroup$ – Listing Nov 29 '11 at 7:50
  • 4
    $\begingroup$ "Take the best answer in this thread and add a factorial at the end"... Is this a good description? :) $\endgroup$ – N. S. Dec 19 '11 at 0:26
  • $\begingroup$ @N.S. a good rule for these types of things: it is only considered larger if it is unreachable by the previous function within reasonable space/characters/things. $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 12:38
  • $\begingroup$ @Listing see the above comment. $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 12:40

12 Answers 12

12
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The fast-growing hierarchy article at WP might also be of interest. $\endgroup$ – r.e.s. Nov 29 '11 at 18:34
  • 7
    $\begingroup$ @r.e.s. Yes, thanks. Wikipedia didn't exist when I originally wrote the above. But it's growing fast. $\endgroup$ – Bill Dubuque Nov 29 '11 at 19:29
  • 5
    $\begingroup$ Another expository article to add to the list Who Can Name the Bigger Number? by Scott Aaronson $\endgroup$ – user18325 Dec 19 '11 at 4:40
  • $\begingroup$ Perhaps look at my updated answer to see some nice diagonalization explained nicely without ordinals. $\endgroup$ – Simply Beautiful Art Apr 5 '17 at 21:06
9
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ $A(A(n,n),A(n,n))$ is probably faster growing ;) $\endgroup$ – Listing Nov 29 '11 at 7:43
  • 4
    $\begingroup$ @Listing: Have you considered $A(A(A(n,n),A(n,n)),A(A(n,n),A(n,n)))$? $\endgroup$ – Elchanan Solomon Dec 19 '11 at 4:44
  • $\begingroup$ All you need to do is pass it Graham's number in both arguments. $\endgroup$ – Cole Johnson Feb 7 '14 at 2:21
  • 3
    $\begingroup$ @ColeJohnson: But then the function would be constant. $\endgroup$ – Raphael Feb 7 '14 at 7:24
  • 1
    $\begingroup$ @Raphael Perhaps you should check my newly updated answer. It should be enlightening :-) And I managed to describe it all in three lines (what you see below at least, in compact mathematical notations) $\endgroup$ – Simply Beautiful Art Apr 5 '17 at 21:10
6
$\begingroup$

The fast growing hierarchy (FGH) is a personal favorite of mine because I think it is not only simple compared to things involving trees or the BB function, while still being able to outgrow, say, the Ackermann function.


First, a simple layman's explanation of what FAIL approximately does:

The lowest level is basic addition:

$Fn\#0=n+1=\text{addition}$

The next level is repeated application of the previous level:

$Fn\#1=F(F(F(\dots)\#0)n\#0)\#0=n\underbrace{+1+1+\dots+1}_n=n+n=2n=\text{multiplication}$

$Fn\#2=F(F(F(\dots)\#1)n\#1)\#1=\underbrace{2\cdot2\cdot\ldots\cdot2}_n\cdot n\approx2^n=\text{exponentiation}$

You can imagine this keeps going, and so I'm going to make a table of stuff:

$$\begin{array}{c|c}k&Fn\#k\approx\\\hline0&n+1\\1&2n\\2&2^n\\3&\underbrace{2^{2^{2^{\dots}}}}_n\\4&\text{Oh God help us}\\5&\text{can't really explain this well anymore}\\\vdots&\vdots\end{array}$$

Where each level is just doing the previous level $n$ times...

But... there is a function that grows faster than every function in the above list. How? Well, it diagonalizes along the list. This function is given by...

$Fn\#0\#1$

At $n=1$, it is equivalent to the $k=1$ level with $n=1$ inside. At $n=2$, it is equivalent to the $k=2$ level with $n=2$ inside.

Eventually, it will catch up to any function in the above list... and then go beyond it. This is the smallest non-primitive-recursive function in FAIL.

We can then nest the function over itself:

$Fn\#1\#1=F(F(\dots)\#0\#1)\#0\#1$

$Fn\#2\#1=F(F(\dots)\#1\#1)\#1\#1$

And eventually, we get a list. We then make a function that grows even faster by making it go from one function in the list to the next, so that it will always grow faster than any fixed level:

$Fn\#0\#2=Fn\#n\#1$

And then iterate over this function to get another list, then diagonalize over it, again and again until you come up with this list:

$$\begin{array}{c|c}k&Fn\#0\#k\approx\\\hline0&n+1\\1&Fn\#0\#1\\2&Fn\#0\#2\\3&Fn\#0\#3\\4&Fn\#0\#4\\5&Fn\#0\#5\\\vdots&\vdots\end{array}$$

Note I did not write most of these out explicitly because they are sooo large...

Anyways, we then diagonalize over this to end up with...

$Fn\#0\#0\#1$

And so on with the story. FAIL actually goes beyond this, extending the notation through @ symbols, and it gets pretty hairy, but to get you thinking, consider the following list:

$$\begin{array}{c|c}k&\text{result}\\\hline1&Fn\#1\\2&Fn\#0\#1\\3&Fn\#0\#0\#1\\\vdots&\vdots\end{array}$$

Have fun diagonalizing this, then iterating it over itself and diagonalizing some more...


The following does, however, require a small bit of comfort level with ordinals, though you needn't have heard of the term before reading this.

FGH is defined by the simple recursive rules:

$f_0(n)=n+1$

$f_{\alpha+1}(n)=\underbrace{f_\alpha(f_\alpha(\dots f_\alpha(n)\dots))}_{n\text{ iterations of }f_\alpha}$

$f_\alpha(n)=f_{\alpha[n]}(n)$

Let's start with some basic examples:

$f_0(5)=5+1=6$

Simple enough.

$f_1(5)=f_0(f_0(f_0(f_0(f_0(5)))))=f_0(f_0(f_0(f_0(6))))=f_0(f_0(f_0(7)))=\dots=10$

Still relatively simple...

$f_3(2)=f_2(f_2(2))=f_2(f_1(f_1(2)))=\dots=2^{11}=2048$

Ok, so if you fill in the $\dots$ part of the previous example, you'll start to notice that it takes quite a while to reach $f_0(n)$ to be able to apply rule one.

You will also notice that in terms of Knuth's up-arrow notation,

$f_k(n)\approx n\uparrow^{k-1}n$

Which so far, isn't too much. We then, however, reach the next stage, where rule 3 comes into play:

Let us define $\omega[n]=n$. It thus follows that

$f_\omega(2)=f_{\omega[2]}(2)=f_2(2)$

Relatively small huh? How about if we try $\omega+1$?

$f_{\omega+1}(2)=f_\omega(f_\omega(2))=f_\omega(f_2(2))=f_\omega(8)=f_8(8)$

And now it got significantly bigger, just at $n=2$. We then have

$f_{\omega\cdot2}(2)=f_{\omega+\omega}(2)=f_{\omega+2}(2)$

In general,

$\omega\cdot(k+1)[n]=\omega\cdot k+n$

And further,

$\omega^{k+1}[n]=\omega^k\cdot n$

To see how $\omega^3$ is expanded, as an example, see Calculation of $f_{\omega^3}(2)$ in the fast growing hierarchy.

What's worse is we can take this to greater heights:

$$\omega^\omega,\omega^{\omega^{\omega^{\dots}}},\text{and beyond}\dots$$

And the unique part is we can define this to go as high as we want. It's all about how far you dare to define the ordinals.

A nice series that not only explains this, but explains how to expand higher and higher ordinals.

Extremely large numbers

Simply Beautiful Art's guide to large numbers, the fast growing hierarchy, and ordinal collapsing functions.

$\endgroup$
  • $\begingroup$ I'm not sure what you mean by "[my] diagonalization technique". Maybe you should clarify that. The examples you mention (and many more) are discussed in the links I gave (and their links). $\endgroup$ – Bill Dubuque Apr 5 '17 at 21:39
  • $\begingroup$ @BillDubuque Oops, don't mind that part :P $\endgroup$ – Simply Beautiful Art Apr 5 '17 at 21:41
  • $\begingroup$ Just wanted to give some nice explanation for those who don't want to go through any links :-) Feel free to critique. $\endgroup$ – Simply Beautiful Art Apr 5 '17 at 21:42
4
$\begingroup$

After having written quite a few programs related to large numbers and recursion over on ppcg.SE, I came up with this really interesting notation which I now call Simply's Ordinal Array Program (SOAP), and I'll explain a tweaked version that's nicer on the eyes than what my actual program does.

Before we begin, we have 2 different types of things we'll deal with.

  • Integers : $\dots,-2,-1,0,1,2,\dots$

  • Ordered sets : $\{1,2,3\}$ or $\{x,y\}$ or $\{-2\}$

Next, we have our ordinal array function:

$$\small f(a,n,b,q)=\begin{cases}q,&a\text{ is a negative integer}\\a-1,&a\text{ is a non-negative integer}\\x,&a=\{x,y,z\},\text{ where $y$ or $z$ are zero}\\\{\{x,y,f(z,n,b,q)\},f(y,n,b,q),x\},&a=\{x,y,z\},\text{ but $y$ and $z$ aren't zero}\\n,&a=\{x,y\},\text{ where $x=0$}\\\{\{f(x,n,x,n),0\},n,n\},&a=\{x,y\},\text{ where $x\ne0$ and $y=0$}\\\{t,n,\{f(y,n,b,t)\}\},&a=\{x,y\},\text{ where $x,y\ne0$ and }t=\{f(x,n,x,n),y\}\\1,&a=\{x\},n=0\\\{f(b,n-1,b,n-1),x\},&a=\{x\}\end{cases}$$

And finally we have our much much simpler ordinal counting function:

$$g(a,n)=\begin{cases}n,&a=0\\g(f(a,n,a,n),n+1),&a\ne0\end{cases}$$

Perhaps a bit of a stretch of what you might call a few lines, but this notation has been well crafted to give you some very very very big numbers, and is strong enough to rival even Deedlit's answer. In fact, $g(\{\{-1,3,1\}\},3n)$ grows approximately as fast as the largest number you can write in Deedlit's $f$ notation using at most $n$ symbols.

Some basic analysis:

If $a$ is an integer, then $g(a,n)=g(a-1,n+1)=\dots=n+a$.

If $a=\{0,0\}$, then $g(a,n)=g(n,n+1)=2n+1$.

If $a=\{\{0,0\},0,k\}$, then $g(a,n)=g(\{0,0\},n+1)=2n+3$.

If $a=\{\{0,0\},1,k\}$, then $g(a,n)=g(\{\{0,0\},1,k-1\},n+2)=\dots=g(\{0,0\},n+2k+1)=2n+4k+3$.

If $a=\{\{0,0\},2,k\}$, then $g(a,n)\approx n\times2^k$.

Okay, not very fast growing so far, but suddenly,

If $a=\{\{0,0\},3,k\}$, then $g(a,n)\approx n\uparrow^kn\approx A(n,n)$, in terms of Knuth's up-arrow notation and the Ackermann function. This is much faster than before.

If $a=\{\{0,0\},3,\{\{0,0\},0,0\}\}$, then $g(a,n)\approx g_n$, with $g_{64}$ being the famous Graham's number.

If $a=\{\{0,0\},4,k\}$, then $g(a,n)\approx f_{\omega^k}(n)$ in the fast growing hierarchy, which is decently fast.

If $a=\{\{0,0\},5,\{0,0\}\}$, then $g(a,n)\approx f_{\varepsilon_0}(2n)$. This is large enough for Peano arithmetic to break down.

If $a=\{\{\{0\},3,\{0,0\}\},2,\{0,0\}\}$, then $g(a,n)\approx TREE(n)$, the famous TREE sequence.

From there, it just keeps going up very rapidly, and

$$g(\{x_n\},n)\approx f_{\psi(\chi(\Omega_{M+1}^{\Omega_{M+1}}))}(n)$$

where

$$x_n=\begin{cases}1,&n=0\\\{x_{n-1},x_{n-1},x_{n-1}\},&n>0\end{cases}$$

which is about as fast as my notation can grow.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "What is the fastest growing total computable function you can describe in a few lines?" I think you miss the computability requirement. $\endgroup$ – Simply Beautiful Art Jun 17 '17 at 21:47
2
$\begingroup$

How farther you can go if we the restriction of computability is lifted? $ \def\nn{\mathbb{N}} $

You can construct extremely fast-growing functions from $\nn$ to $\nn$. Clearly, you can enumerate the computable functions (since there are countably many) and diagonalize against those that halt, giving you a function that grows faster (eventually) than every computable function. So it dwarfs everything in the FGH (fast-growing hierarchy), and you can only begin to appreciate how fast that is when you appreciate how fast the functions in the FGH grow!

But there's much much more we can do, and in only a few lines:


Pick some infinite countable ordinal $α$ and some bijection $i$ from finite strings to $α$. Define a hyper-program as a program that can call an oracle $H$, where $H(k,x)$ is $1$ iff $x$ is a valid hyper-program that when run on empty input only calls $H(j,\bullet)$ for string $j$ such that $i(j) < i(k)$, and halts, and $H(k,x)$ is $0$ otherwise. Identifying finite strings with natural numbers, let $F(n)$ be $1$ plus the sum of the outputs of all the hyper-programs from $0$ to $n$ on input $n$ (excluding those that do not halt).


To understand how fast $F$ grows, we have to look first at the growth rate of the hyper-programs. A hyper-program that does not call $H$ at all are ordinary programs (computably equivalent to Turing machines). We shall say that a hyper-program is at level $β$ iff on all inputs it only calls $H(k,\bullet)$ for $i(k)<β$. Ordinary programs are hence at level $0$. $H(i^{-1}(0),\bullet)$ is the halting oracle, also known as the first Turing jump. The Busy Beaver function $BB$ can be computed using calls to $H(i^{-1}(0),\bullet)$, so it is at level $1$. But programs which can call $BB$ as an oracle also cannot solve their own halting problem, yet $H(i^{-1}(1),\bullet)$ (the second Turing jump) can! So by the same diagonalization as for $BB$, there is a hyper-program that calls only $H(i^{-1}(1),\bullet)$ and computes a function that outgrows every function computed by programs that calls only $BB$.

Can you imagine how fast that is? Every program that you can design using $BB$ that always halts on every input, including iterating $BB$ on the input as many times as given by the output of some computable function in the FGH, will lose hands down to a simple hyper-program at level $2$... In general, there is a hyper-program at level $β$ that grows faster than every total hyper-program at any level lower than $β$. Now can you imagine level $3,4,5,\cdots$?

Note that we have to pick $α,i$ right from the beginning, and the hyper-programs we get will reach all levels below $α$. For example we could have picked $α$ to be the Church-Kleene ordinal $ω_1^{CK}$. If we want to reach higher, simply pick a larger $α$ to start with! But there is no largest countable ordinal, so there is no absolute winner.

Also, for each natural number $n$, if the $n$-th hyper-program halts on input $n$ and outputs $x$ then $F(n) > x$ by construction. Therefore $F$ grows faster than every total hyper-program! But notice that we could have simply started with $α+1$ and in the new hierarchy $F$ would simply be at level $α$. So it all boils down to the length of α.

Finally, if one has no qualms with programs over an uncountable alphabet, one can do exactly the same construction but with uncountable $α$. But at that point one is relying on some set theoretic assumptions such as the axiom schema of replacement in ZF.

$\endgroup$
2
$\begingroup$

It is pretty simple to define one:

BIGCOQ(n) = For any valid, well-typed Coq program with a term x:Nat and its length not longer than n, the maximum value of x.

This function is totally computable, and it will growth faster than every other function that could be written in Coq code...

$\endgroup$
2
$\begingroup$

Using ordinals, we can construct some pretty massive things. Much in the same manner that Deedlit has answered, we may then construct the following fast growing function based on finitely many $\text{Ord}^m\mapsto\text{Ord}$ functions:

$$C(n)=\begin{cases}\{0,1,2\},&n=0\\=C(n-1)\cup\{f_1(X_1),f_2(X_2),\dots,f_k(X_k):X_i\in C(n-1)^{m_i}\},&n>0\end{cases}$$

where $A^m$ is the set of $m$-tuples who's elements are elements of $A$. One may then define

$$H(\alpha,n)=\begin{cases}n,&\alpha=0\\H(\max(C(n)\cap\alpha),2^n),&\alpha\ne0\end{cases}$$

which produces an infinite hierarchy of fast growing functions satisfying some nice properties, like:

$$\alpha<\beta\implies H(\alpha,n)\le H(\beta,n)\\n<k\implies H(\alpha,n)<H(\alpha,k)$$

If the provided functions are computable, then you have yourself some very fast growing computable functions. Even something as simple as $f_1(\alpha,\beta)=\alpha+\beta$ and $f_2(\alpha)=\omega^\alpha$ will produce a function who's growth rate is comparable to the Goodstein sequence.

Using this ordinal collapsing function, we get the following:

$H(0,n)=n$

$H(1,n)=2^n$

$H(2,n)=2^{2^n}$

$H(3,n)=2^{2^{2^n}}$

$H(\omega,n)\approx2\uparrow\uparrow n$

$H(\omega^2,n)\approx2\uparrow\uparrow\uparrow n$

$H(\omega^k,n)\approx2\uparrow^{k+1}n$

$H(\omega^\omega,n)\approx Ack(n,n)$, the Ackermann function.

$H(\omega^{\omega+1},n)\approx g_n$, where $g_{64}$ is Graham's number.

$H(\psi_0^0(0),n)\approx\mathcal {G}(n)$, the length of the Goodstein sequence starting at $n$.

$H(\psi_0^0(\omega^{\omega^{\Psi(0)+1}+1}),n)\approx{\rm tree}(n),~H(\psi_0^0(\omega^{\omega^{\Psi(0)+1}}+,n)\gtrsim{\rm TREE}(n)$, the tree and weak tree function.

$H(\psi_0^0(\psi_{\Psi(\omega)}^0(0)),n)\approx{\rm scg}(n)$, the subcubic graph numbers.

$\endgroup$
1
$\begingroup$

I'm gonna take another look at this problem. That is, consider the fast growing total computable function I can describe in a few lines of Ruby code. It's pretty large. Let's start with this small appetizer:

def f(a,b)a.times{a*=b<0?a:f(a,b-1)}&&a end

Function alone: https://repl.it/Hvr5/63

Function with inputs: https://repl.it/Hvr5/62

This function grows pretty fast and only requires 43 characters to write (including spaces). It basically works as follows:

f(a,-1) = a^(2^a)

f(a,b) >/≈ f(f(f(...f(a,b-1),...,b-1),b-1),b-1), with a nestings of f(-,b-1)

In terms of the Ackermann function, f(a,b) ≈ A(b+4,a). An explicit expansion:

f(2,2) > f(f(2,1),1) > f(f(f(2,0),0),1) > f(f(f(f(2,-1),-1),0),1) = f(f(f(16,-1),0),1) = f(f(2^2^18,0),1) > ...

We can make a slightly larger function:

def f(a,b,c=a)c>0?a.times{a*=f a,b,c-1}&&a:b<0?a:f(a,b-1)end

Function alone: https://repl.it/Hvr5/67

Function with inputs: https://repl.it/Hvr5/66

Now we're at 60 characters (including spaces). Still pretty small. It basically works as follows:

f(a,-1,0) = a

f(a,-1,1) = a^(2^a)

f(a,b,c) >/≈ f(f(f(...f(a,b,c-1),...,b,c-1), with a nestings of f(-,b,c-1)

f(a,b,0) = f(a,b-1,a)

So f(a,-1,b+1) ≈ f(a,b) from before, but we then can make much larger numbers. It quickly catches up to Graham's number, which is approximately f(64,0,1). Let's look at an expansion:

f(2,0,1) > f(f(2,0,0),0,0) = f(f(2,-1,2),0,0) > f(f(f(2,-1,1),-1,1),0,0) = f(f(16,-1,1),0,0) = f(2^2^18,0,0) = f(2^2^18,-1,2^2^18) ≈ A(2^2^18,2^2^18)

Okay, that wasn't so bad, but you'll quickly find that gets out of hand very fast...

We could try throwing in a few more arguments while we're at it:

def f(a,b=a,c=a,d=a,e=a,g=a,h=a,i=a,j=a,k=a,l=a,m=a,n=a,o=a,p=a,q=a)a.times{a**=q>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o,p,q-1):p>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o,p-1):o>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o-1):n>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n-1):m>0?f(a,b,c,d,e,g,h,i,j,k,l,m-1):l>0?f(a,b,c,d,e,g,h,i,j,k,l-1):k>0?f(a,b,c,d,e,g,h,i,j,k-1):j>0?f(a,b,c,d,e,g,h,i,j-1):i>0?f(a,b,c,d,e,g,h,i-1):h>0?f(a,b,c,d,e,g,h-1):g>0?f(a,b,c,d,e,g-1):e>0?f(a,b,c,d,e-1):d>0?f(a,b,c,d-1):c>0?f(a,b,c-1):b<0?a:f(a,b-1)}&&a end

Function alone: https://repl.it/Hvr5/58

Function with input: https://repl.it/Hvr5/59

This one's a whopping 494 characters (including spaces), but if you take a look at the code... its just... really repetitive... of nothing new compared to the above. This would be where one defines this function for arbitrarily many arguments... which gives way to a whole new scheme of what you can do...


And to save space, one can incorporate half a variable by taking advantage of negative numbers. For example, if the second argument is negative, replace it with the first argument. If the second argument is zero, do the normal base case. If the second argument is greater than zero, do the normal case.

def f(a,b=-a,c=a,d=a,e=a,g=a,h=a,i=a,j=a,k=a,l=a,m=a,n=a,o=a,p=a,q=a)a.times{a**=q>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o,p,q-1):p>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o,p-1):o>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n,o-1):n>0?f(a,b,c,d,e,g,h,i,j,k,l,m,n-1):m>0?f(a,b,c,d,e,g,h,i,j,k,l,m-1):l>0?f(a,b,c,d,e,g,h,i,j,k,l-1):k>0?f(a,b,c,d,e,g,h,i,j,k-1):j>0?f(a,b,c,d,e,g,h,i,j-1):i>0?f(a,b,c,d,e,g,h,i-1):h>0?f(a,b,c,d,e,g,h-1):g>0?f(a,b,c,d,e,g-1):e>0?f(a,b,c,d,e-1):d>0?f(a,b,c,d-1):c>0?f(a,b,c-1):b<0?f(a,a):b<1?a:f(a,b-1)}&&a end

Function alone: https://repl.it/Hvr5/72

Function with inputs: https://repl.it/Hvr5/74


Of course, all of the above can be drastically reduced down to a function that intakes arrays as arguments of arbitrary length:

def f(a,b=Array.new(a,a),c=a)d,*e=b;a.times{a+=(b.class==Fixnum)?a:b.size<2?f(a,d,c):d<0?f(a,e,c+1):c<0?a:f(a,[a,d-1,e],c-1)};a end

Function alone: https://repl.it/Jfgb/4

Function with inputs: https://repl.it/Jfgb/6

Function with handy dandy stuff on the side: https://repl.it/Jfgb/8

Lengthy explanations: https://repl.it/Jfcr/3


In terms of the fast growing hierarchy,

$$f(a,b)\approx f_{b+2}(a)$$

$$f(a,b,c)\approx f_{\omega b+c}(a)$$

$$f(a,b,c,d,e,g,h,i,j,k,l,m,n,o,p,q)\approx f_{\omega^{14}b+\omega^{13}c+\dots+\omega^2 o+\omega p+q}(a)$$

$$f(a,-b,c,d,e,g,h,i,j,k,l,m,n,o,p,q)\approx f_{\omega^{15}+\omega^{13}c+\dots+\omega^2 o+\omega p+q}(a)$$

Not really sure on the arbitrary length array yet.


Inspired by Largest printable number.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ BEAF?? Bower's exploding array function? $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 16:49
0
$\begingroup$

Few lines??? I'm not even an ingenious mathematician and I can do this in half a line: $$x!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!$$ , let alone what an ingenious mathematician will do with few lines. Maybe, you should put more restriction to your character limit.

I think this function suits the description of fastest growing as it's value at $x=0$ is 1. At $x=1$, it disguises you by staying constant. It takes your trust by growing by just 1 at $x=2$. Now, it has your trust and you, who wanted a decently growing function, would chose this one and reject other candidates like $10^x$, $x^2$, etc. But as soon as you step further, it shows its true nature and grows up to God knows where at $x=3$.

If the faster growing function competition was a race where all the functions had to start at 0 and reach 1 Googol ($10^{100}$) the fastest and functions with less than 5 characters where allowed, my money would be on $\tan{x}$ because we all know how slow it is at $x=1.4$, that's when $10^x$ would think it's far ahead, but just after $x=1.57$, $\tan{x}$ would look like it just teleported to $1 Googol$. As for, $x!!!!$, I don't think it's of much use if the race starts at 0.

When you think about it, the simplest function which easily grows up fastest to infinity starting from 0 is a well-known trigonometric function and it beats $\tan{x}$ by a slight margin and its name is $\sec{x}$.

At $x=1.57$, $\tan{x}$ is merely 1255, whereas $\tan^{-1}(\text{Googol})=1.5707963267948966192313216916398$. So, by merely increasing $x$ by 0.000707963267948966192313216916398, $\tan{x}$ grows from 1255 to 1Googol. So, I guess I was correct when I said $\tan{x}$ teleports to 1Googol.

$\endgroup$
  • 1
    $\begingroup$ Let $n!_k$ be $n$ followed by $k$ factorials. In terms of the fast growing hierarchy, as my answer explains, we have $$n!_n\ll f_4(n)$$ so indeed, this is not much. Also, since the poles of $\tan$ are order one, $\tan(x)$ will not grow as fast as you'd think. $\endgroup$ – Simply Beautiful Art Mar 6 '17 at 12:02
  • $\begingroup$ @SimplyBeautifulArt I was talking about a simple well-known function which approaches infinity the fastest. Can you think of any other simple function whose value at 1.4 is merely 5 or 6 while near 1.57 it grows up to infinity? It's clearly the fastest growing. $\endgroup$ – Dove Mar 12 '17 at 3:00
  • 1
    $\begingroup$ @SimplyBeautifulArt At $x=1.57$, $\tan{x}$ is merely 1255, whereas $tan^{-1}(1Googol)=1.5707963267948966192313216916398$. So, by merely increasing $x$ by 0.000707963267948966192313216916398, $\tan{x}$ grows from 1255 to 1Googol. $\endgroup$ – Dove Mar 12 '17 at 3:07
  • $\begingroup$ You miss my point. You are approaching $\pi/2$ linearly, as in one digit at a time, and $\tan(x)$ will only grows as fast as $10^{10^{\text{number of digits}}}$, which is far slower than anything here. Indeed, if we interpolate linear between the integer inputs of any of the answers here, you will find some can easily jump over a Graham's number of distance in $10^{-10}$. $\endgroup$ – Simply Beautiful Art Mar 12 '17 at 11:48
  • 1
    $\begingroup$ I'm sorry if I sounded harsh. I just wanted to explain why $\tan(x)$ grows slowly :-) $\endgroup$ – Simply Beautiful Art Mar 14 '17 at 13:32

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.