What is Ackermann's Function?


The Ackermann function is the simplest example of a well-defined total function which is computable but not primitive recursive. See the article "A function to end all functions" by G�nter Dotzel, Algorithm 2.4, Oct 1991, Pg 16. The function f(x) = A(x, x) grows much faster than polynomials or exponentials. The definition is: 


	1. If x = 0 then  A(x, y) = y + 1
	2. If y = 0 then  A(x, y) = A(x-1, 1)
	3. Otherwise,     A(x, y) = A(x-1, A(x, y-1))

See: Ackermann Function -- From MathWorld
See: Ackermann Function -- From Wikipedia, the free encyclopedia

Return to Ackermann's Function
Return to Harry's Home Page

This page accessed times since October 20, 2004.
Page created by: [email protected]
Changes last made on Wednesday, 18-Jun-08 09:52:35 PDT
Hosted by www.Geocities.ws

1