I was reading couple of books which cover algorithm development and, particulary, the theory of complexity of different algorithms. I wonder, what is the fastest growing function you know, which is actually used for any algorithm or, just in general - for computing something useful.

Just to highlight - that function should actually compute something useful and not be a purely synthetic example (so the answer 'pick up any answer from this thread and thow a factorial at the end' is not valid).

Right now the only thing which comes into my mind is a factorial (which we use to calculate tons of different things, but first of all - number of permutations). But maybe there is something which grows even faster?

  • 1
    $\begingroup$ What do you mean by a funtion being "used for" an algorithm? That the algorithm computes the function as part of its operation, or that the function is related to the complexity of the algorithm? $\endgroup$ – Henning Makholm Oct 26 '15 at 21:10
  • 1
    $\begingroup$ How is computing number of permutations more "useful" than computing lower bounds for the dimension of a hypercube such that <plug in the definition of the Graham's number here>? $\endgroup$ – Andrey Tyukin Oct 26 '15 at 21:19

A few really fast growing functions came up for David Moews's BIGNUM BAKEOFF contest. Here is the link to Moews's home page, in particular here is a results page, commented by Moews.

The point of the contest was to write, in 512 characters, a C code which would output a number as large as one can get. As you can guess, most entries work by first defining a fast growing function and then providing some input to it. Often, the results are incomprehnsibly large.

Of particular interest might be the (winning) entry due to Ralph Loader. His program implements, in very compact way (in Loader's own words) "a parser, type-checker, interpreter and proof-search for the Huet-Coquand "Calculus of Constructions" (CoC)". You can find out more by reading a README from this package, provided by Loader. Although I can't tell you much about CoC, I cann tell you that it roughly works like a strong proof system, and some of its properties make it possible to decide whether a sentence is provable or not. Thanks to this, it can define many fast growing functions. Loader's program basicaly diagonalizes through the whole system.

This is, to my knowledge, the fastest growing function ever implemented in an actual code.

As for recursive functions which might have not been implemented, you can get ones in the following manner: let $T$ be any recursively enumerable, $\omega$-consistent theory. Take a Turing machine which, for input $n$, looks at the $\Sigma^0_1$ (i.e. ones of the form $\exists k:\phi(k)$ for $\phi$ with bounded quantifiers only) sentences which are provable from $T$ in at most $n$ steps (for some reasonable interpretation of "steps"), and then seeks for the least witness to these formulas, and takes the largest one. It's easy to convince yourself that these functions can be fast-growing if $T$ is a strong theory.

However, the above are kind of "artificial" examples. More natural examples come from work of Harvey Friedman. In the course of his "foundational adventures", as he calls them, he finds examples of recursive functions which eventually dominate all recursive functions which are provably total in some large cardinal extensions of ZFC. To name two quite strong examples out of many, let me attract your attention to finite promise games and greedy clique sequences. If you look through his FOM mailing lists, you might be able to find even more!

For a more general reference, I would like to recommend you Googology Wiki, which is an encyclopedia-like wiki with the goal of collecting information about large numbers and fast-growing functions, both recursive and non-recursive ones. If you are interested, come and take a look :)

  • $\begingroup$ Thanks! Perfect answer and tons of interesting reading material :) $\endgroup$ – Maksim Khaitovich Oct 27 '15 at 6:58

The Busy Beaver function, and similar functions such as Ackermann's, are very useful for getting publications and advanced degrees.

(This is a modification of a statement of Landau's.)

  • $\begingroup$ Heh. Gotta give this +1. $\endgroup$ – Rick Decker Oct 27 '15 at 0:37
  • $\begingroup$ Never heard about busy beaver, will dig through it. Extremely interesting stuff. $\endgroup$ – Maksim Khaitovich Oct 27 '15 at 7:01

The Presburg arithmetic (https://en.wikipedia.org/wiki/Presburger_arithmetic) is decidable but the complexity to decide whether a given statement is true or false has double exponential growth in the worst case.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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