2
$\begingroup$

Actually, this is not precisely my question. If $a(x)$ is the inverse ackermann function, then obviously $a(a(x))$ grows slower than $a(x)$, as does $\log(a(x))$, and so on. But is there a function f that goes to infinity and cannot be asymptotically bounded below (when x goes to infinity) from any finite composition of logarithms, inverse Ackermann functions, and arithmetic operations?

(Equivalently, is there a "well-behaved" function that cannot be bounded above by a finite composition of Ackermann functions, exponentials, arithmetic operations, etc?)

Edit: I mean functions that are defined for all (positive) reals, not just integers.

Edit 2: Okay, infinitely differentiable functions.

$\endgroup$
  • 3
    $\begingroup$ Diagonalize: Given any countably many functions $f:\mathbb N\to\mathbb N$, there is a function that grows faster than all of them. $\endgroup$ – Andrés E. Caicedo Jun 3 '14 at 7:13
  • $\begingroup$ Very true. I guess my question is more about curiosity - do you know of an actual example? Especially one that is actually studied in mathematics? $\endgroup$ – user2258552 Jun 3 '14 at 7:14
  • $\begingroup$ The busy-beaver function grows faster than any computable function, while any finite composition of Ackermann functions is computable. $\endgroup$ – user21820 Jun 3 '14 at 7:16
  • $\begingroup$ Is inverse busy-beaver also not computable? $\endgroup$ – Bennett Gardiner Jun 3 '14 at 7:20
  • 2
    $\begingroup$ @BennettGardiner: If we can compute the inverse BB function, we can compute the BB function itself because it is monotonic. Thus the inverse BB function is also non-computable. $\endgroup$ – user21820 Jun 3 '14 at 7:21
1
$\begingroup$

Let $F(n) = A^n(n)$ for any natural $n$

Then $F(n) \in ω(A^k(n))$ as natural $n \to \infty$ for any natural $k$

Let $f(n) = \min( \{ k : k \in \mathbb{N} \wedge F(k) \ge n \} )$

Then $f(n) \in o(a^k(n))$ as natural $n \to \infty$ for any natural $k$

$\endgroup$
  • $\begingroup$ I provided this answer just for a concrete example. Anyway the busy-beaver function grows faster than this too. $\endgroup$ – user21820 Jun 3 '14 at 7:16
  • 1
    $\begingroup$ Thanks. Well, that was a rather naive question. I probably should have thought about it a little instead of impulsively posting here first. $\endgroup$ – user2258552 Jun 3 '14 at 7:17
  • $\begingroup$ @antawn: And for real functions we can just use $F(x) = A^{\lfloor x \rfloor}(\lfloor x \rfloor)$. $\endgroup$ – user21820 Jun 3 '14 at 7:18
  • $\begingroup$ Yes, of course, sorry - edited again to say infinitely differentiable functions. (I realize it seems like I'm just rejecting all your ideas, but this was the way I was thinking about it in my head, and I just did not flesh out the details thoroughly). $\endgroup$ – user2258552 Jun 3 '14 at 7:21
  • 2
    $\begingroup$ @antawn: For infinitely differentiable functions I think you can use bump functions to smoothly move between the steps. I know you'll say it's still not elegant hahaha.. $\endgroup$ – user21820 Jun 3 '14 at 7:22
2
$\begingroup$

Check out the Busy Beaver function.

$\endgroup$
  • $\begingroup$ Good point, I have edited my question - I meant only functions defined for all R. Although of course you could just interpolate, so how about infinitely differentiable functions. $\endgroup$ – user2258552 Jun 3 '14 at 7:18
  • $\begingroup$ The ackermann function and its inverse are defined on $\mathbb N$. $\endgroup$ – Yuan Gao Jun 3 '14 at 7:24
  • 1
    $\begingroup$ @antawn you can always interpolate between integer points with an infinitely differentiable function $\endgroup$ – vonbrand Jun 3 '14 at 9:53
  • $\begingroup$ @vonbrand How exactly does one interpolate between an infinite number of integer points with an infinitely differentiable function? $\endgroup$ – user2258552 Jun 3 '14 at 17:31
  • $\begingroup$ @user2258552 Using linear combinations of en.wikipedia.org/wiki/Bump_function (or its indefinite integral which yields a smooth step function). Unlike fully analytic functions, infinitely smooth functions can easily be manipulated locally, leaving plenty of room to interpolate between many well-spaced targets. $\endgroup$ – Erick Wong Oct 3 '16 at 23:20
0
$\begingroup$

In the fast growing hierarchy, we have

$$A(n,n)\approx f_\omega(n)$$

So for any $\alpha>\omega$, $A(n,n)\ll f_\alpha(n)$, and by taking the inverse (with a rounding just like how one takes the inverse of the Ackermann function) you can easily make functions that grow slower than $A^{-1}(n)$.

See Create the slowest growing function you can in under 100 bytes for some more examples.

$\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.