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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.