What is the slowest growing function that is total but not primitive recursive?

Question

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?

Answer 1

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.