properties of Ackermann function


In this entry, we derive some basic properties of the Ackermann functionMathworldPlanetmath A(x,y), defined by double recursion, as follows:

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

These properties will be useful in proving that A is not primitive recursive.

  1. 1.

    A is total (dom(A)=2).

  2. 2.

    A(1,y)=y+2.

  3. 3.

    A(2,y)=2y+3.

  4. 4.

    y<A(x,y).

  5. 5.

    A(x,y)<A(x,y+1).

  6. 6.

    A(x,y+1)A(x+1,y).

  7. 7.

    A(x,y)<A(x+1,y).

  8. 8.

    A(r,A(s,y))<A(r+s+2,y)

  9. 9.

    For any r,s, A(r,y)+A(s,y)<A(t,y) for some t not depending on y.

Most of the proofs are done by inductionMathworldPlanetmath.

Proof.
  1. 1.

    Induct on x. First, A(0,y)=y+1 is well-defined, so (0,y)dom(A) for all y. Next, suppose that for a given x, (x,y)dom(A) for all y. We want to show that (x+1,y)dom(A) for all y. To do this, induct on y. First, (x+1,0)dom(A), since A(x+1,0)=A(x,1) is well-defined. Next, assume that (x+1,y)dom(A). Then A(x,A(x+1,y))=A(x+1,y+1) is well-defined. so (x+1,y+1)dom(A) as well.

  2. 2.

    Induct on y. First, A(1,0)=A(0,1)=2. Next, assume A(1,y)=y+2. Then A(1,y+1)=A(0,y+2)=y+3=(y+1)+2.

  3. 3.

    Induct on y. First, A(2,0)=A(1,1)=1+2=3. Next, assume A(2,y)=2y+3. Then A(2,y+1)=A(1,A(2,y))=A(2,y)+2=(2y+3)+2=2(y+1)+3.

  4. 4.

    Induct on x. First, y<y+1=A(0,y). Next, assume y<A(x,y), where x>0. Then y+1A(x,y)<A(x-1,A(x,y))=A(x,y+1).

  5. 5.

    Induct on x. First, A(0,y)=y+1<y+2=A(0,y+1). Next, assume that A(x,y)<A(x,y+1). Then A(x+1,y)<A(x,A(x+1,y))=A(x+1,y+1).

  6. 6.

    Induct on y. First, A(x,1)=A(x+1,0). Next, assume that A(x,y+1)A(x+1,y). Then A(x,y+2)A(x,A(x,y+1))A(x,A(x+1,y))=A(x+1,y+1).

  7. 7.

    Induct on x. First, A(0,y)=y+1<y+2=A(1,y). Next, assume that A(x,y)<A(x+1,y). There are two cases: y=0. Then A(x+1,0)=A(x,1)<A(x+1,1). Otherwise, y=z+1, so that A(x+1,y)=A(x+1,z+1)=A(x,A(x+1,z))A(x,A(x,z+1))=A(x,A(x,y))<A(x,A(x+1,y))=A(x+1,y+1).

  8. 8.

    A(r,A(s,y))<A(r+s,A(s,y))<A(r+s,A(r+s+1,y))=A(r+s+1,y+1)A(r+s+2,y).

  9. 9.

    Let z=max{r,s}. Then A(r,y)+A(s,y)2A(z,y)<2A(z,y)+3=A(2,A(z,y))<A(4+z,y). The proof is completed by setting t=4+z.

With respect to the recursive property of A, we see that A is recursive, since, by Church’s Thesis, A can be effectively computed (in fact, a program can be easily written to compute A(x,y)). We also have the following:

Proposition 1.

Define An:NN by An(m)=A(n,m). Then An is primitive recursive for each n.

Proof.

A0(m)=m+1=s(m), so is primitive recursive. Now, assume An is primitive recursive, then An+1(0)=A(n+1,0)=A(n,1)=An(1)=k, and An+1(m+1)=A(n+1,m+1)=A(n,A(n+1,m))=An(A(n+1,m))=An(An+1(m)), so that An+1 is defined by primitive recursion via the constant function constk, and An, which is primitive recursive by the induction hypothesis. Therefore An+1 is primitive recursive also. ∎

The most important fact about A concerning recursiveness is that A is not primitive recursive. Due to the length of its proof, it is demonstrated in this entry (http://planetmath.org/AckermannFunctionIsNotPrimitiveRecursive).

Title properties of Ackermann function
Canonical name PropertiesOfAckermannFunction
Date of creation 2013-03-22 19:07:25
Last modified on 2013-03-22 19:07:25
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Result
Classification msc 03D75