We shall now prove that the Ackermann function is not primitive recursive.
First note that we define the size of a function as follows:
For unary functions, we simply expect the inequality to hold for every value, so that at at all points. Now with this in mind we can show the Ackermann function is not primitive recursive because all primitive recursive functions are in fact smaller than the Ackermann function.
The Ackermann Function
The Ackermann Function is Effectively calculable
We present the result of some initial calculations:
- Ack(0, 0) = 0+1 = 1
- Ack(1, 0) = Ack(0, 1) = 1+1 = 2
- Ack(3, 0) = Ack(2, 1) = Ack(1, Ack(2, 0)) =Ack(1, Ack(1, 1)) = Ack(1, Ack(o, Ack(1, 0)) = Ack(1, Ack(0, Ack(0, 1)) = Ack(1, 3) = Ack(0, Ack(1, 2)) = Ack(0, Ack(0, Ack(1, 1))) = Ack(0, Ack(0, Ack(0, Ack(1, 0)))) = Ack(0, Ack(0, Ack(0, Ack(0, 1)))) = Ack(0, Ack(0, Ack(0, 2))) = Ack(0, Ack(0, 3)) = Ack(0, 4) = 5.
As should be clear the complexity of the calculation increases swiftly as we progress up the function space. For instance the value So while there is an a method which will achieve the result of the Ackermann function, it is not evident that anyone has the appropriate resources of time or memory in which to calculate the values. In particular we shall show that:
where PR is the set of primitive recursive functions.
Proof
There are five cases, the first three are trivial since clearly
Similarly the successor function does not increase at the same speed as the Ackermann function either, so we need only check the possibilities that (i) a composition of primitive recursive functions or (ii) a recursive concatenation of primitive recursive functions “increases at greater speeds” than the Ackermann function. We shall show that no such function exists, and hence that the Ackermann function is not a primitive recursive function.
First we prove (i).
Let such that where are the first parameters of the Ackermann function. Then let then we shall show first that
We make a small notational amendment for the composition of Ackermann functions. Let
Now we wish to show two things which will help us in our proof. Observe that
- where both are positive.
We know that (1) follows from that the fact that . To see this pattern assume , then we have The result (1) follows easily by induction.
To show that (2) recall the definition of the Ackermann function and consider the value of This completes the proof of (2), since the simple case where the number of Ackermann compositions is 0, i.e. satisfies the condition obviously.
With these two facts established we can finish proof: We begin by noting our initial inequalities:
but then by our first observation we can observe that
but since
we can conclude, by observation two that:
which completes the proof, since there is a value of the Ackermann function which is strictly greater than the composition of any two primitive recursive functions operating on the same input.
It remains to prove (ii).
For this we assume that there is a function defined by the recursion equations. So we have
Then since is primitive recursive (assume it’s increasing), we know there is an Ackermann function larger than and we shall show that for some
The proof is by induction.
Base case: We know that is a constant function, which is a primitive recursive unary projection function, so by the earlier observations there is an Ackermann function, call it bigger than . This completes the base case.
Induction Hypothesis: Assume the observation holds for all cases
Induction Step: Let Observe that
Then,
since is increasing, but then by the induction hypothesis we know that:
then by substitution and our choice for m, we have:
from which we know by the definition of the Ackermann function and substitution that:
So we can conclude that , which completes the proof.
What to Conclude:
From this observation we can see the inductive method used in defining the Ackermann function uses a method stronger than primitive recursion. The question remains how do we characterise the method that was used to define the Ackermann function? We discuss this in another post.