Ackermann function is total recursive

In this entry, we give a formal proof that the Ackermann functionMathworldPlanetmath A(x,y), given by


is both a total functionMathworldPlanetmath and a recursive functionMathworldPlanetmath. Actually, the fact that A is total is proved in this entry ( It remains to show that A is recursive.

Recall that the computation of A(x,y), given x,y, can be thought of as an iterated operationMathworldPlanetmath performed on finite sequencesPlanetmathPlanetmath of integers, starting with x,y and ending with z=A(x,y) (see this entry ( It is this process we will utilize to prove that A is recursive.

In the proof below, the following notations and definitions are used to simplify matters:

  • if s is the sequence r1,,rm, then E(s) or r1,,rm denote the code number of s given the encoding E;

  • lh(n) is the length of the sequence whose code number is n;

  • (n)i is the i-th number in the sequence whose code number is n;

  • (n)-i is the i-th to the last number in the sequence whose code number is n (so that (n)-1 is the last number in the sequence whose code number is n);

  • red(n) is the code number of the sequence obtained by deleting the last number of the sequence whose code number is n;

  • ext(n,a) is the code number of the sequence obtained by appending a to the end of the sequence whose code number is n.

If E is a primitive recursive encoding, then each of the above function is primitive recursive. For example, (n)-i=(n)lh(n)-˙i+1.

Theorem 1.

A is recursive.


In this proof, the choice of encoding E is the multiplicative encoding, for it is convenient and, more importantly, a primitive recursive encoding. Briefly,


where pi is the i-th prime number (so that p1=2).

We know that computing A(x,y)=z is basically a sequence of computations on finite sequences:


Let s(x,y,i) denote the sequence at step i, then the above sequence can be rewritten:


Define f(x,y,i)=E(s(x,y,i)). From this we see that


is the function that computes the smallest number of steps needed so that the code number becomes stationary. When the code number is decoded, we get the resulting value of A(x,y):


where D(m):=(m)-1, decodes m, and returns the last number in the sequence s whose code number E(s) is m.

Now the remaining task to show that f is primitive recursive. First, note that


is primitive recursive. Next, we want to express


where h is the function that changes the code number of the sequence s(x,y,n) to the code number of the sequence s(x,y,n+1). Once we obtain h and show that h is primitive recursive, then f is primitive recursive, as it is defined by primitive recursion via primitive recursive functions x,y and h.

To find out what h is, recall the four rules of constructing the next sequence from the current one givne in this this entry ( Let n1=E(s(x,y,k)) and n2=E(s(x,y,k+1)). We rewrite the four rules using the notations and definitions here:

  1. 1.

    if lh(n1)=1, then n2=n1;

  2. 2.

    if lh(n1)>1, and (n1)-2=0, then n2=h1(n1), where

  3. 3.

    if lh(n1)>1, and (n1)-2>0 and (n1)-1=0, then n2=h2(n1), where



  4. 4.

    if lh(n1)>1, and (n1)-2>0 and (n1)-1>0, then then n2=h3(n1), where


If we define predicatesMathworldPlanetmathPlanetmath:

  1. 1.


  2. 2.

    Φ1(n):=lh(n)>1, and (n)-2=0,

  3. 3.

    Φ2(n):=lh(n)>1, and (n)-2>0 and (n)-1=0,

  4. 4.

    Φ3(n):=lh(n)>1, and (n)-2>0 and (n)-1>0.

Then each Φi is primitive recursive, pairwise exclusive, and Φ0¬Φ1¬Φ2¬Φ3. Now, define h as follows:

h(n):={id(n)if Φ0(n),h1(n)if Φ1(n),h2(n)if Φ2(n),h3(n)if Φ3(n).

Since h is defined by cases, and each hi is primitive recursive, h is also primitive recursive. ∎

Title Ackermann function is total recursive
Canonical name AckermannFunctionIsTotalRecursive
Date of creation 2013-03-22 19:07:53
Last modified on 2013-03-22 19:07:53
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 15
Author CWoo (3771)
Entry type TheoremMathworldPlanetmath
Classification msc 03D75
Related topic AckermannFunctionIsNotPrimitiveRecursive