For what I have in mind is the Ackermann-Buck function. If there isn't a slowest growing function do you have examples of other function slower growing than Ackermann-Buck's function?

  • A function that returns a cryptographic hash of the Ackerman-Buck functions output would be total, not primitive recursive and would not grow. – Q the Platypus May 26 '16 at 1:28

There can't be such a function. A rough proof by contradiction follows.

Assume $ f : \mathbb{N} \to \mathbb{N} $ is the smallest growing total recursive function that is not primitively recursive. Then you can construct $ g : \mathbb{N} \to \mathbb{N} $ such that.

$$ g(x) = \begin{cases} f(x/2) & \text{x is even} \\ f((x-1)/2) & \text{x is odd} \end{cases} $$

$g$ will grow half as quickly as $f$ but will not be primitively recursive. However since $f$ was assumed to be the smallest growing non primative function this is a contradiction.

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.