TOPICS
Search

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

 A(x,y)={y+1   if x=0; A(x-1,1)   if y=0; A(x-1,A(x,y-1))   otherwise.
(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)=2^(2^(·^(·^(·^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))
(7)
=A(1,y-1)+1
(8)
=A(0,A(1,y-2))+1
(9)
=A(1,y-2)+2
(10)
=...
(11)
=A(1,0)+y
(12)
=A(0,1)+y=y+2.
(13)

A(2,y) has a similar derivation:

A(2,y)=A(1,A(2,y-1))
(14)
=A(2,y-1)+2
(15)
=A(1,A(2,y-2))+2
(16)
=A(2,y-2)+4
(17)
=...
(18)
=A(2,0)+2y
(19)
=A(1,1)+2y
(20)
=2y+3.
(21)

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)),
(22)

but with the slightly different boundary values

F(0,y)=y+1
(23)
F(1,0)=2
(24)
F(2,0)=0
(25)
F(x,0)=1    for x=3,4,....
(26)

Buck's recurrence gives

F(1,y)=2+y
(27)
F(2,y)=2y
(28)
F(3,y)=2^y
(29)
F(4,y)=2^(2^(·^(·^(·^2))))_()_(y).
(30)

Taking F(4,n) gives the sequence 1, 2, 4, 16, 65536, 2^(65536), ... (OEIS A014221), while F(n,n) for n=0, 1, ... then gives 1, 3, 4, 8, 65536, 2^(2^(·^(·^(·^2))))_()_(m), ... (OEIS A001695). Here, m=2^(2^(·^(·^(·^2))))_()_(65536), which is a truly huge number!


See also

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

Explore with Wolfram|Alpha

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

Referenced on Wolfram|Alpha

Ackermann Function

Cite this as:

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

Subject classifications