(Recursively) defined as follows,
A(0,n) = n+1
A(m+1,0) = A(m,1)
A(m+1,n+1) = A(m, A(m+1,n)),
Ackermann's function grows
very quickly. In fact,
A(1,n) = A(0, A(0, ..., A(0,n)...)) = 2n
A(2,n) = A(1, A(1, ..., A(1,n)...)) = 2^(n+1)
...
with each successive step proceeding along the hierarchy
addition,
multiplication,
exponentiation, ...
Ackermann's function is recursive (equivalently, computable), but it is not primitive recursive. In fact, if we define f_k(n) = A(k,n) then for each k, f_k is primitive recursive. It is defined for all inputs; this shows that while every primitive recursive function is a total computable function, the converse is not true.