I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive recursive functions etc.

But, coming at it from the point of view of the 'ground requirements' which define the collection of recursive functions, I am having a hard time making the link between the (current) definition for the Ackermann function, and why it requires unbounded minimisation/search.

I am unfamiliar with a lot of theoretical computer science so I hope my question makes sense!

  • $\begingroup$ It grows so fast that it is not contained in the set of primitive recursive functions, because they all cannot grow that fast. So something must be used that exceeds the capabilities of primitive recursive functions. $\endgroup$ – gnasher729 Sep 2 '20 at 23:09

Roughly speaking, a function is primitive recursive if it can be computed by a program in which all loops are bounded ahead of time. Concretely, we can consider the LOOP programming language, which has the following instructions:

  • Set $x$ to zero.
  • Increment $x$.
  • Run a piece of code $x$ times.

We can use LOOP to compute one-argument functions using some input/output convention, say the input is in $x$ and the output is in $y$.

If the program has no loops, then $y \leq x + C$ for some constant $C$. If the program has no nested loops, then $y = O(x)$. If it has nesting depth 2 (a loop can appear within another loop, but that's it), then $y = O(x^C)$ for some constant $C$. More generally, if the program has nesting depth $d$, then $y$ can be bounded by a function on level $d$ on the Ackermann hierarchy.

The Ackermann function is constructed in such a way that it doesn't belong to the Ackermann hierarchy, and so cannot be computed by a LOOP program. In brief, it grows too fast.

Growing too fast isn't the only reason for not being primitive recursive. Indeed, using diagonalization we can construct Boolean recursive functions which are not primitive recursive. Let $f_i$ be an effective enumeration of all primitive recursive functions, and define $$ f(n) = \begin{cases} 1 & \text{if } f_n(n) = 0, \\ 0 & \text{otherwise}. \end{cases} $$ The function $f$ is recursive but, by construction, not primitive recursive.


Your Answer

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

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