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: hjsmithh@sbcglobal.net
Changes last made on Wednesday, 18-Jun-08 09:52:35 PDT