computing the Ackermann function

Recall that the Ackermann functionMathworldPlanetmath (the modern version) A(x,y) is given by the following double recursive relation:


From the equations above, we see that computing the Ackermann function involves first deciding whether the pair (x,y) is such that

x=0,or  x>0 and y=0,or  x>0 and y>0,

which dictates which one of the three equations above to use. Let us illustrate this by a simple example: x=1 and y=1:


If x=2, then quite a few more steps are involved:

A(2,1) = A(1,A(2,0))=A(1,A(1,1))=A(1,A(0,A(1,0)))=A(1,A(0,A(0,1)))
= A(1,A(0,2))=A(1,3)=A(0,A(1,2))=A(0,A(0,A(1,1)))
= A(0,A(0,A(0,A(1,0))))=A(0,A(0,A(0,A(0,1))))
= A(0,A(0,A(0,2)))=A(0,A(0,3))=A(0,4)=5.

When x>2, computations of A(x,y) becomes unwieldy, mainly due to the number of steps involved, and partially due to the number of A’s and the parentheses that need to be written down.

Nevertheless, based on the computations of A(1,1) and A(2,1) above, we see an algorithmMathworldPlanetmath emerging for computing A(x,y) in general. First, notice that in each of the expression A(,)), the right parentheses all occur at the right end of the expression. Therefore, there is no ambiguity involved if the A’s and the parentheses were removed. Formalizing this notion, we have

Definition. Suppose z is in the range of A. We say that a sequence x1,,xn is an Ackermann sequence for z if


In particular, the sequence z of length 1 is an Ackermann sequence for z.

Therefore, computing A(x,y)=z is just a process of transforming the Ackermann sequence x,y to the Ackermann sequence z, for z. Transforming one sequence 𝒙 to another sequence 𝒙 can be formalized as follows:

Definition. Suppose 𝒙 is a finite non-empty sequence of non-negative integers. A sequence 𝒙 is said to be immediately derivable from 𝒙, written 𝒙𝒙, if exactly one of the following conditions holds:

  1. 1.

    𝒙 consists of one number, and 𝒙=𝒙;

  2. 2.

    𝒙=𝒚,0,z, and 𝒙=𝒚,z+1;

  3. 3.

    𝒙=𝒚,y,0, with y>0, and 𝒙=𝒚,y-1,1; or

  4. 4.

    𝒙=𝒚,y,z, with y>0, z>0, and 𝒙=𝒚,y-1,y,z-1,

where 𝒚 may be the empty sequence.

It is clear that conditions 2-4 correspond to the three equations defining the Ackermann function.

We also write 𝒙𝒙 to mean a finite chain of sequences


such that either m=1, or m>1, and 𝒙i𝒙i+1 for i=1,,m-1.

From the definition above, we can also describe the entire computational process rigorously:

  1. 1.

    start with a sequence x,y, call the sequence derived at step k=0;

  2. 2.

    If 𝒙 is derived at step k, and 𝒙𝒙, then 𝒙 is derived at step k+1.

For example, the computation of A(1,1) can be written simply as


A number of easy consequences of can now be listed:

  • if 𝒙𝒙, then 𝒙𝒙 unless 𝒙 consists of only one number.

  • if 𝒙𝒙, then 𝒙 is an Ackermann sequence for z iff 𝒙 is.

  • if 𝒙z, where z, then 𝒙 is an Ackermann sequence for z.

  • if x>0, then there is t such that x,yx-1,t.

  • any pair x,y is an Ackermann sequence for some z.

Title computing the Ackermann function
Canonical name ComputingTheAckermannFunction
Date of creation 2013-03-22 19:07:46
Last modified on 2013-03-22 19:07:46
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Algorithm
Classification msc 03D75