info prev up next book cdrom email home

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

\begin{displaymath}
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}
\end{displaymath} (1)

Special values for Integer $x$ include
$\displaystyle A(0,y)$ $\textstyle =$ $\displaystyle y+1$ (2)
$\displaystyle A(1,y)$ $\textstyle =$ $\displaystyle y+2$ (3)
$\displaystyle A(2,y)$ $\textstyle =$ $\displaystyle 2y+3$ (4)
$\displaystyle A(3,y)$ $\textstyle =$ $\displaystyle 2^{y+3}-3$ (5)
$\displaystyle A(4,y)$ $\textstyle =$ $\displaystyle \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,
$\displaystyle A(1,y)$ $\textstyle =$ $\displaystyle A(0,A(1,y-1))=A(1,y-1)+1$  
  $\textstyle =$ $\displaystyle A(0,A(1,y-2))+1 = A(1,y-2)+2$  
  $\textstyle =$ $\displaystyle \ldots = A(1,0)+y=A(0,1)+y=y+2.$  
      (7)

$A(2,y)$ has a similar derivation,
$\displaystyle A(2,y)$ $\textstyle =$ $\displaystyle A(1,A(2,y-1))=A(2,y-1)+2$  
  $\textstyle =$ $\displaystyle A(1,A(2,y-2))+2=A(2,y-2)+4=\ldots$  
  $\textstyle =$ $\displaystyle 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)

\begin{displaymath}
F(x,y)=F(x-1, F(x, y-1)),
\end{displaymath} (9)

but with the slightly different boundary values
$\displaystyle F(0,y)$ $\textstyle =$ $\displaystyle y+1$ (10)
$\displaystyle F(1,0)$ $\textstyle =$ $\displaystyle 2$ (11)
$\displaystyle F(2,0)$ $\textstyle =$ $\displaystyle 0$ (12)
$\displaystyle F(x,0)$ $\textstyle =$ $\displaystyle 1 \qquad {\rm for\ }x=3, 4, \ldots.$ (13)

Buck's recurrence gives
$\displaystyle F(1,y)$ $\textstyle =$ $\displaystyle 2+y$ (14)
$\displaystyle F(2,y)$ $\textstyle =$ $\displaystyle 2y$ (15)
$\displaystyle F(3,y)$ $\textstyle =$ $\displaystyle 2^y$ (16)
$\displaystyle F(4,y)$ $\textstyle =$ $\displaystyle \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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25