Ackermann Function

The Ackermann function is the simplest example of a well-defined Total Function which is Computable but not Primitive Recursive, providing a counterexample to the belief in the early 1900s that every Computable Function was also Primitive Recursive (Dötzel 1991). It grows faster than an exponential function, or even a multiple exponential function. The Ackermann function $A(x,y)$ is defined by

$$A(x,y)\equiv\cases{ y+1 & if $x=0$\cr A(x-1, 1) & if $y=0$\cr A(x-1, A(x, y-1)) & otherwise.\cr}$$ (1)

Special values for Integer $x$ include

$$A(0,y) = y+1$$ (2)

$$A(1,y) = y+2$$ (3)

$$A(2,y) = 2y+3$$ (4)

$$A(3,y) = 2^{y+3}-3$$ (5)

$$A(4,y) = \underbrace{{2}^{{2}^{\cdot^{\cdot^{\cdot^{2}}}}}\!\!}_{y+3}-3.$$ (6)

Expressions of the latter form are sometimes called Power Towers. $A(0,y)$ follows trivially from the definition. $A(1,y)$ can be derived as follows,

$$A(1,y) = A(0,A(1,y-1))=A(1,y-1)+1$$

$$= A(0,A(1,y-2))+1 = A(1,y-2)+2$$

$$= \ldots = A(1,0)+y=A(0,1)+y=y+2.$$ (7)

$A(2,y)$ has a similar derivation,

$$A(2,y) = A(1,A(2,y-1))=A(2,y-1)+2$$

$$= A(1,A(2,y-2))+2=A(2,y-2)+4=\ldots$$

$$= A(2,0)+2y=A(1,1)+2y=2y+3.$$ (8)

Buck (1963) defines a related function using the same fundamental Recurrence Relation (with arguments flipped from Buck's convention)

$$F(x,y)=F(x-1, F(x, y-1)),$$ (9)

but with the slightly different boundary values

$$F(0,y) = y+1$$ (10)

$$F(1,0) = 2$$ (11)

$$F(2,0) = 0$$ (12)

$$F(x,0) = 1 \qquad {\rm for\ }x=3, 4, \ldots.$$ (13)

Buck's recurrence gives

$$F(1,y) = 2+y$$ (14)

$$F(2,y) = 2y$$ (15)

$$F(3,y) = 2^y$$ (16)

$$F(4,y) = \underbrace{{2}^{{2}^{\cdot^{\cdot^{\cdot^{2}}}}}\!\!}_{y}.$$ (17)

Taking $F(4,n)$ gives the sequence 1, 2, 4, 16, 65536, $2^{65536}$, .... Defining $\psi(x)=F(x,x)$ for $x=0$, 1, ... then gives 1, 3, 4, 8, 65536, $\underbrace{{2}^{{2}^{\cdot^{\cdot^{\cdot^{2}}}}}\!\!}_{m}$, ... (Sloane's A001695), where $m=\underbrace{{2}^{{2}^{\cdot^{\cdot^{\cdot^{2}}}}}\!\!}_{65536}$, a truly huge number!

See also Ackermann Number, Computable Function, Goodstein Sequence, Power Tower, Primitive Recursive Function, TAK Function, Total Function

References

Buck, R. C. ``Mathematical Induction and Recursive Definitions.'' Amer. Math. Monthly 70, 128-135, 1963.

Dötzel, G. ``A Function to End All Functions.'' Algorithm: Recreational Programming 2.4, 16-17, 1991.

Kleene, S. C. Introduction to Metamathematics. New York: Elsevier, 1971.

Péter, R. Rekursive Funktionen. Budapest: Akad. Kiado, 1951.

Reingold, E. H. and Shen, X. ``More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case.'' SIAM J. Comput. 20, 156-183, 1991.

Rose, H. E. Subrecursion, Functions, and Hierarchies. New York: Clarendon Press, 1988.

Sloane, N. J. A. Sequence A001695/M2352 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Smith, H. J. ``Ackermann's Function.'' http://pweb.netcom.com/~hjsmith/Ackerman.html.

Spencer, J. ``Large Numbers and Unprovable Theorems.'' Amer. Math. Monthly 90, 669-675, 1983.

Tarjan, R. E. Data Structures and Network Algorithms. Philadelphia PA: SIAM, 1983.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 11, 227, and 232, 1991.