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

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

## 1 Answer

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.