The Ackermann Function is not Primitive recursive.

Posted in Logic, Mathematics, Things that are true by

We shall now prove that the Ackermann function is not primitive recursive.

First note that we define the size of a function as follows:

g(x_{1} .... x_{k}) \text {is smaller than } f(x) \text{ if } \forall(\overrightarrow{x_{i}}) \text{ having maximum entry } x_{i} = m \text{ then } g(x_{1} .... x_{m}) < f(m)

For unary functions, we simply expect the inequality to hold for every value, so that g(n) < f(n) 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

Ack(0, x) = x+1 \\ Ack(n, 0) = Ack(n-1, 1) \\ Ack(n, x) = Ack( n- 1, Ack(n, x-1))

The Ackermann Function is Effectively calculable

We present the result of some initial calculations:

  1. Ack(0, 0) = 0+1 = 1
  2. Ack(1, 0) = Ack(0, 1) = 1+1 = 2
  3.  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 Ack(5, 0) = Ack(4, 1) = 65533. 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:

Ack(\infty, x) = Ack(x, x) > pr(x) \; \forall pr \in PR

where PR is the set of primitive recursive functions.

Proof

There are five cases, the first three are trivial since clearly Ack(x , x) > Z(x) \wedge Ack( x , x) > p_{i}^{k}(x_{i}) \text{ for any value } k.

Similarly the successor function S(x) 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 f = g(h) such that g < Ack_{i}, h < Ack_{j}. where i, j \in \mathbb{N} are the first parameters of the Ackermann function. Then let m > max \{i, j \} then we shall show first that f(x) < Ack_{m+1}(x)

We make a small notational amendment for the composition of Ackermann functions. Let

\underbrace{Ack_{m}^{x}(1) = Ack_{m}(Ack_{m}(...Ack_{m}, (1))))}_{\text{ x times }}

Now we wish to show two things which will help us in our proof. Observe that

  1. x < Ack_{m}^{x-1}(1) where both are positive.
  2. Ack_{m}^{x+1}(1) = Ack_{m+1}(x)

We know that (1) follows from that the fact that Ack_{0}^{x-1}(1) = x. To see this pattern assume x = 3, then we have Ack_{0}^{2}(1) = Ack(0, Ack(0, 1)) = Ack(0, 2) = 3. The result (1) follows easily by induction.

To show that (2) recall the definition of the Ackermann function and consider the value of Ack_{m+1}(x) = Ack(m+1, x) = Ack(m, Ack(m+1, x - 1) = Ack(m , Ack(m , Ack(m+1, x - 2) = .... \underbrace{Ack(m, Ack(m... Ack(m+1, 0)))}_{\text{ x times }} = Ack_{m}^{x}(Ack(m+1, 0). This completes the proof of (2), since the simple case where the number of Ackermann compositions is 0, i.e. A_{m}^{0}  satisfies the condition obviously.

With these two facts established we can finish proof: We begin by noting our initial inequalities:

g(h(x)) < Ack_{i}(Ack_{j}(x)) < Ack_{m}(Ack_{m}(x))

but then by our first observation we can observe that

Ack_{m}(Ack_{m}(x)) < Ack_{m}(Ack_{m}(Ack_{m}^{x-1}(1)))

but since

Ack_{m}(Ack_{m}(Ack_{m}^{x-1}(1))) = Ack_{m}^{x+1}

we can conclude, by observation two that:

Ack_{m}(Ack_{m}(x)) < Ack_{m+1}(x)

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 f(x)  defined by the recursion equations. So we have

f(0) = c \\ f(n+1) = g(n, f(n))

Then since g is primitive recursive (assume it’s increasing), we know there is an Ackermann function Ack_{i}(x) larger than g and we shall show that f(x) < Ack_{m}(x)  for some m > 0.

The proof is by induction.

Base case: We know that f(0) is a constant function, which is a primitive recursive unary projection function, so by the earlier observations there is an Ackermann function, call it Ack_{j}(0) bigger than f(0). This completes the base case.

Induction Hypothesis:  Assume the observation holds for all cases k \leq f(n).

Induction Step: Let m > max \{i+1, j \}. Observe that f(n+1) = g(n, f(n))

Then,

g(n, f(n)) < g(f(n), f(n))

since g is increasing, but then by the induction hypothesis we know that:

g(n, f(n)) < Ack_{i}(f(n)) < Ack_{i}(Ack_{m}(n))

then by substitution and our choice for m, we have:

g(n, f(n)) < Ack_{m-1}(Ack_{m}(n))

from which we know by the definition of the Ackermann function and substitution that:

g(n, f(n)) < Ack_{m}(n+1)

So we can conclude that f(n+1) < Ack_{m}(n+1), 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.

2 thoughts on “The Ackermann Function is not Primitive recursive.”

  1. Pingback: Intuitive Algorithms and Primitive Recursion | Aspiring PI

  2. Pingback: Aspiring PI – Applying the Squeezing Argument to Intuitive Algorithms/Calculable Functions | Marbles in a Jar

Leave a comment