# Is there an equation $f(k,m,n)=n$ where $n$ is the number of applications of the Ackermann function needed?

Using the definition of the Ackermann function on page 247 of this paper, (sidenote, great paper): $$\alpha(k,m,n) = \begin{cases} m+n, & k=1 \\ m, & n=1 \\ \alpha(k-1,m,\alpha(k,m,n-1)),& \text{otherwise} \end{cases}$$

Is there some function $f$ such that $f(k,m,n)$ returns the number of times $\alpha$ is used to calculate $\alpha(k,m,n)$?

Some trivial values would be $f(1,m,n)=f(k,m,1)=1$, and $f(2,2,2)=2$, found manually by counting the number of $\alpha$s in the expanded form of $\alpha$.

Note: There is neither a tag for "ackermann-function" or "recursion", I lack the privilege to create these but I feel they would have some limited use.

• Your question doesn't make a whole lot of sense in the vocabulary of mathematics. Does there exist a function? Sure. You have just defined such a function. You mean is there a nice neat closed form? How many times does a recursive algorithm call upon itself might be a good CS question. I think your question might get more play on cs.stackexchange.com but I am not so sure of the community there and how they would respond. – Mason Jul 15 at 4:40
• @Mason I initially intended to ask this on stackoverflow, but I felt it wasn't CS-related enough – user189728 Jul 15 at 14:55
• Oh no. Ackermann Function is right out of the CS Camp. They should be very interested: Check out: cs.stackexchange.com/questions/47227/…. The problem will be that you are going to have a more precise question to make much progress. – Mason Jul 15 at 17:58
• @Mason is there a simple way to migrate questions? – user189728 Jul 15 at 17:59
• Look it up on the Meta and post the link here. I dunno know. but I need to. – Mason Jul 15 at 17:59