An example of a total computable function that is not primitive recursive; appears in the literature in many variants. The original three-argument variant can be used to define the Ackermann numbers.
The three argument version originally due to Ackermann is defined as follows.
Let $\varphi$ take three non-negative integers $m,n,p$ as arguments. We define
$$\begin{align} \varphi(m,n,0) &= m + n \\ \varphi(m,n,1) &= m \times n \\ \varphi(m,n,2) &= m^n\end{align}$$
This can be extended to the higher values of $p$ by the description
$$ \varphi(m,n,p+1) = \underbrace{\varphi(m,\varphi(m,\varphi(m,\varphi(\dots}_{\text{Nested }~ n-1~ \text{ times}}),p),p),p) $$
Thus for $p = 3$ this defines the tetration operation, and for $p > 3$ this continues the natural generalisation.
While the above serve as a good description of the Ackermann function, the original recursive definition, without the need of the cumbersome underbrace shown in the formula above, is the following:
$$ \varphi(m,n,p) = \begin{cases} m+n & p = 0\\ 0 & n = 0, p = 1\\ 1 & n = 0, p = 2\\ m & n = 0, p > 2\\ \varphi(m,\varphi(m,n-1,p),p-1) & \text{The general case if none of the above is satisfied}\end{cases}$$
One can check that this agrees with the informal description given above.
In this notation, the Ackermann numbers are defined as the sequence $$ \big(\varphi(n,n,n+1)\big)_{n\in \mathbb{N}} $$ The first few are: $$ \begin{align} \varphi(1,1,2) &= 1^1 = 1 \\ \varphi(2,2,3) &= \varphi(2,2,2) = 2^2 = 4\\ \varphi(3,3,4) &= \varphi(3,\varphi(3,3,3),3)\\ & = \varphi(3,\varphi(3,\varphi(3,3,2),2),3) \\ & = \varphi(3,\varphi(3,27,2),3) \\ & = \varphi(3,3^{27},3) = 3^{3^{3^{\dots^3}}} \end{align}$$ where in the last expression the numeral "$3$" appears a total of $3^{27} \approx 7.6\times 10^{12}$ times.
Many other variants of the Ackermann function have since been defined. For the clarity of discussion, when asking a question about Ackermann functions, please be sure to specify the precise variant used.
