Ackermann function (http://en.wikipedia.org/wiki/Ackermann_function) defined as

$ A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} $

is total recursive but not primitive recursive. To see this we could prove by induction on the complexity of primitive recursive functions that each primitive recursive function is eventually dominated by this function (we need a bit coding to keep the number of arguments consistent). Essentially this function manages to capture the ``fast-growing'' property. Note that the index set for recursive functions is not recursive while that for primitive recursive function is.

Ackermann function defined as

$ A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} $

is total recursive but not primitive recursive. To see this we could prove by induction on the complexity of primitive recursive functions that each primitive recursive function is eventually dominated by this function (we need a bit coding to keep the number of arguments consistent). Essentially this function manages to capture the ``fast-growing'' property. Note that the index set for recursive functions is not recursive while that for primitive recursive function is.

Ackermann function (http://en.wikipedia.org/wiki/Ackermann_function) defined as  $ A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} $ is total recursive but not primitive recursive. To see this we could prove by induction on the complexity of primitive recursive functions that each primitive recursive function is eventually dominated by this function (we need a bit coding to keep the number of arguments consistent). Essentially this function manages to capture the ``fast-growing'' property. Note that the index set for recursive functions is not recursive while that for primitive recursive function is.

Ackermann function (http://en.wikipedia.org/wiki/Ackermann_function) defined as 

$ A(m, n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases} $

is total recursive but not primitive recursive. To see this we could prove by induction on the complexity of primitive recursive functions that each primitive recursive function is eventually dominated by this function (we need a bit coding to keep the number of arguments consistent). Essentially this function manages to capture the ``fast-growing'' property. Note that the index set for recursive functions is not recursive while that for primitive recursive function is.