# Is the inverse ackermann function the slowest growing function that goes to infinity?

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.

• Diagonalize: Given any countably many functions $f:\mathbb N\to\mathbb N$, there is a function that grows faster than all of them. – Andrés E. Caicedo Jun 3 '14 at 7:13
• 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? – user2258552 Jun 3 '14 at 7:14
• The busy-beaver function grows faster than any computable function, while any finite composition of Ackermann functions is computable. – user21820 Jun 3 '14 at 7:16
• Is inverse busy-beaver also not computable? – Bennett Gardiner Jun 3 '14 at 7:20
• @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. – user21820 Jun 3 '14 at 7:21

## 3 Answers

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$

• I provided this answer just for a concrete example. Anyway the busy-beaver function grows faster than this too. – user21820 Jun 3 '14 at 7:16
• Thanks. Well, that was a rather naive question. I probably should have thought about it a little instead of impulsively posting here first. – user2258552 Jun 3 '14 at 7:17
• @antawn: And for real functions we can just use $F(x) = A^{\lfloor x \rfloor}(\lfloor x \rfloor)$. – user21820 Jun 3 '14 at 7:18
• 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). – user2258552 Jun 3 '14 at 7:21
• @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.. – user21820 Jun 3 '14 at 7:22

Check out the Busy Beaver function.

• 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. – user2258552 Jun 3 '14 at 7:18
• The ackermann function and its inverse are defined on $\mathbb N$. – Yuan Gao Jun 3 '14 at 7:24
• @antawn you can always interpolate between integer points with an infinitely differentiable function – vonbrand Jun 3 '14 at 9:53
• @vonbrand How exactly does one interpolate between an infinite number of integer points with an infinitely differentiable function? – user2258552 Jun 3 '14 at 17:31
• @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. – Erick Wong Oct 3 '16 at 23:20

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.