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!