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>0

See 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

----
CategoryMath