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

61 Views Asked by At

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.