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