(Recursively) defined as follows,

A(0,n) = n+1Ackermann's function grows

A(m+1,0) = A(m,1)

A(m+1,n+1) = A(m, A(m+1,n)),

*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.