24
$\begingroup$

I just had this interesting question. What is the fastest growing function known to man? Is it busy beaver?

We know functions such as $x^2$, but this function grows slower than $2^x$, which in turn grows slower than $x!$, which in turn grows slower than $x^x$. We can then combine functions, to have $(x^x)!$ that grows faster than $x^x$, and so on.

Then we arrive at recursive functions such as Ackermann's function $A(x,x)$ that grows much faster than $(x^x)!$. Then people though about busy beaver $B(x)$ function that grows even faster than Ackermann's function.

At this point I haven't heard of any other functions that grow faster than busy beaver. Does it mean that there are no other functions that can possibly grow quicker than busy beaver? (Aside from factorial of $B(x)$ and like $A(B(x), B(x))$, etc.)

$\endgroup$

migrated from cstheory.stackexchange.com Sep 22 '12 at 22:10

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 25
    $\begingroup$ Busy beaver^2 grows faster $\endgroup$ – artistoex Sep 23 '12 at 10:54
  • 2
    $\begingroup$ @vzn Why would growth only make sense for computable functions? Asymptotic growth is a mathematical concept unrelated to computability at all. $\endgroup$ – Raphael Sep 23 '12 at 16:07
  • 8
    $\begingroup$ @vzn for BB the growth rate implies uncomputability. but uncomputability does not imply high growth rate. $\endgroup$ – Sasho Nikolov Sep 23 '12 at 16:41
  • 6
    $\begingroup$ Hi @vzn. The function $f$ such that $f(n) = 1$ if the $n$'th Turing machine halts, and $f(n) = 0$ otherwise is uncomputable but grows more slowly than the Ackerman function. On the other hand, it is easy to prove that for some fixed constant $c$, for all $n > c$, BB$(n) > $ Ackerman$(n)$. If this were not the case, you could solve the halting problem by running a turing machine $T$ with description length $n$ for only Ackerman$(n)$ steps and seeing if it halted before then or not. $\endgroup$ – Aaron Sep 23 '12 at 21:49
  • 4
    $\begingroup$ @vzn maybe you have another idea of "grows faster".. what I (and I believe others) mean is the partial order given by $f = \omega(g)$. $\endgroup$ – Sasho Nikolov Sep 24 '12 at 2:19
49
$\begingroup$

The busy beaver function grows faster than any computable function. However, it can be computed by a Turing machine which has been given access to an oracle for solving the halting problem. You can then define a "second order" busy beaver function, that grows faster than any function that can be computed even by any Turing machine with an oracle for the halting problem. You can keep doing this forever, building up a hierarchy of ever faster growing busy beaver functions.

See Scott Aaronson's excellent essay on this topic, Who Can Name the Bigger Number?.

$\endgroup$
  • $\begingroup$ Do you have a resource/reasoning as to why an oracle TM for HALT_TM can solve busy beaver? $\endgroup$ – Ryan Feb 22 '15 at 4:44
  • 1
    $\begingroup$ Ryan: Solving the halting problem is (computationally) equivalent to knowing Busy Beaver. 1) Does program[length=n] halt? Simulate it for BusyBeaver(n) steps. 2) What is BusyBeaver(n)? For every program of length<n, throw it away if it halts, and take the max score amongst the others. $\endgroup$ – ninjagecko Dec 13 '15 at 16:01
  • $\begingroup$ @ninjagecko do you mean not halts $\endgroup$ – PyRulez Jun 18 '17 at 2:31
35
$\begingroup$

There is no such thing as "the fastest growing function". In fact, there is even no sequence of fastest growing functions. This was already shown by Hausdorff. Given two functions $f,g\colon \mathbb{N} \longrightarrow \mathbb{N}$, say that $g$ grows faster than $f$ if $$ \lim_{n\rightarrow\infty} \frac{g(n)}{f(n)} = \infty. $$ Given a function $f$, the following function $g$ grows faster than $f$: $$ g(n) = nf(n). $$ Given a sequence of functions $f_n$, the following function $g$ grows faster than all of them: $$ g(n) = n \max_{m \leq n} f_m(n). $$ A natural question to ask is whether there is a "scale" of fastest growing functions. This is a well-ordered set of functions $g_\alpha$ which is "cofinal", that is, given any function $f$, there is a faster-growing function $g_\alpha$. (Instead of a well-ordered set, we can equivalently talk about a chain, that is, any two functions in the set need to be comparable.) The existence of a scale is independent of ZFC: assuming CH, there is a scale, while in Cohen's model that falsifies CH (adding $\omega_1$ reals), no scale exists.

$\endgroup$
5
$\begingroup$

Other answers address the question directly. For more and deeper background, this paper by Lafitte on the subject considers the larger context of busy beaver-like functions. It also has some results and theorems fitting the idea into a more general framework. It shows that (informally) "busy beaver-like functions" have a close connection to Chaitin incompleteness phenomena (Theorem 2.1). It also shows that there are theories that are not "powerful" enough to "comprehend" the busy beaver-like functions, i.e. they are unprovable in those theories due to Godel-related incompleteness. It shows the idea of assuming busy beaver-like results as axioms and a logical progression of theories that results similar to ideas originally envisioned by Turing.

[1] Busy beavers gone wild by Grégory Lafitte. Abstract:

We show some incompleteness results à la Chaitin using the busy beaver functions. Then, with the help of ordinal logics, we show how to obtain a theory in which the values of the busy beaver functions can be provably established and use this to reveal a structure on the provability of the values of these functions.

$\endgroup$
  • $\begingroup$ the other answer is completely different. hmmm, speaking of "emphasis on language", would an example of that be a moderator saying "hell no"? anyway the abbrevs can be seen as a generous gift to people who like to earn +2 for edits =) $\endgroup$ – vzn Sep 28 '12 at 16:48
  • 1
    $\begingroup$ You say yourself that this does not answer directly, so why did you not post as a comment? $\endgroup$ – Raphael Sep 29 '12 at 10:09
0
$\begingroup$

The Hartmanis-Stearns time and space hierarchy theorems prove that there is no "fastest growing" function in terms of time or space because the scale is unbounded. But it does give an ordering such that all "well behaved" computable/recursive functions can be compared. But many "fast growing" math functions do not seem to have been evaluated in terms of time/space complexity so far despite it being a somewhat obvious or even glaring theoretical "gap" to fill. Doing so could lead to important "bridge theorems".

$\endgroup$

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.