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 for integer and by

(1)

Special values for integer include

			(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)
			(8)
			(9)
			(10)
			(11)
			(12)
			(13)

has a similar derivation:

			(14)
			(15)
			(16)
			(17)
			(18)
			(19)
			(20)
			(21)

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

(22)

but with the slightly different boundary values

			(23)
			(24)
			(25)
			(26)

Buck's recurrence gives

			(27)
			(28)
			(29)
			(30)

Taking gives the sequence 1, 2, 4, 16, 65536, , ... (Sloane's A14221), while for , 1, ... then gives 1, 3, 4, 8, 65536, , ... (Sloane's A001695). Here, , which is a truly huge number!

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. Princeton, NJ: Van Nostrand, 1964.

Péter, R. Rekursive Funktionen in der Komputer-Theorie. 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. Sequences A001695/M2352 and A014221 in "The On-Line Encyclopedia of Integer Sequences."

Smith, H. J. "Ackermann's Function." http://www.geocities.com/hjsmithh/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.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 906, 2002.

CITE THIS AS:

Weisstein, Eric W. "Ackermann Function." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AckermannFunction.html