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 
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, 
, ... (OEIS A014221),
while 
for 
, 1, ... then
gives 1, 3, 4, 8, 65536, 
,
... (OEIS A001695). Here, 
,
which is a truly huge number!
Contact the MathWorld Team
Ackermann function
(2,2)
