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 is defined by

(1) |

(2) | |||

(3) | |||

(4) | |||

(5) | |||

(6) |

Expressions of the latter form are sometimes called Power Towers. follows trivially from the definition. can be derived as follows,

(7) |

has a similar derivation,

(8) |

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

(9) |

(10) | |||

(11) | |||

(12) | |||

(13) |

Buck's recurrence gives

(14) | |||

(15) | |||

(16) | |||

(17) |

Taking gives the sequence 1, 2, 4, 16, 65536, , .... Defining for , 1, ... then gives 1, 3, 4, 8, 65536, , ... (Sloane's A001695), where , a truly huge number!

**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.

© 1996-9

1999-05-25