Ackermann function is total recursive


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

A(0,y)=y+1,A(x+1,0)=A(x,1),A(x+1,y+1)=A(x,A(x+1,y))

is both a total functionMathworldPlanetmath and a recursive functionMathworldPlanetmath. Actually, the fact that A is total is proved in this entry (http://planetmath.org/PropertiesOfAckermannFunction). 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 (http://planetmath.org/ComputingTheAckermannFunction)). 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.

Proof.

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

E(r1,,rm)=p1r1+1pmrm+1,

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:

x,yzz

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

s(x,y,0)s(x,y,1)s(x,y,k)

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

g(x,y)=μi[f(x,y,i)=f(x,y,i+1)].

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):

A(x,y)=D(f(x,y,g(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

f(x,y,0)=x,y=2x+13y+1

is primitive recursive. Next, we want to express

f(x,y,n+1)=h(f(x,y,n)),

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 (http://planetmath.org/ComputingTheAckermannFunction). 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

    h1(n):=ext(red2(n),(n)-1+1);
  3. 3.

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

    h2(n):=ext(ext(red2(n),(n)-2-1),1);

    or

  4. 4.

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

    h3(n):=ext(ext(ext(red2(n),(n)-2-1),(n)-2),(n)-1-1).

If we define predicatesMathworldPlanetmathPlanetmath:

  1. 1.

    Φ0(n):=lh(n)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