The Ackermann function (named after mathematician Wilhelm Ackermann) is the simplest known example of a well defined total function which is computable, but not **Primitive Recursive** (calculable using only **for** loops with a fixed upper limit).

Ackermann(0, j) = j + 1 Ackermann(i, 0) = Ackermann(i - 1, 1) for i>0 Ackermann(i, j) = Ackermann(i - 1, Ackermann(i, j - 1)) for i>0 and j>0See ReallyBigNumbers for some more discussion of Ackermann's function

*Interesting... anyone care to give a BigOh value for this function?*

Also see

- http://mathworld.wolfram.com/AckermannFunction.html
- http://mathworld.wolfram.com/PrimitiveRecursiveFunction.html
- http://www.wikipedia.org/wiki/Ackermann_function

EditText of this page (last edited July 10, 2013) or FindPage with title or text search