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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Mason Jul 15 '18 at 4:40
  • 1
    $\begingroup$ @Mason I initially intended to ask this on stackoverflow, but I felt it wasn't CS-related enough $\endgroup$ – user189728 Jul 15 '18 at 14:55
  • $\begingroup$ 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. $\endgroup$ – Mason Jul 15 '18 at 17:58
  • $\begingroup$ @Mason is there a simple way to migrate questions? $\endgroup$ – user189728 Jul 15 '18 at 17:59
  • $\begingroup$ Look it up on the Meta and post the link here. I dunno know. but I need to. $\endgroup$ – Mason Jul 15 '18 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.