The original Ackermann function $\varphi\colon \mathbb{N}\times\mathbb{N}\times\mathbb{N}\_0\to \mathbb{N}$ as defined in [1] was invented to prove that there is a function that is recursive but not primitive recursive.
It can be given by the following recursion:


* $\varphi(a,b,0) = a+b$
* $\varphi(a,b,n+1) = (x\mapsto \varphi(a,x,n))^b(\alpha(a,n))$


Where $\alpha(a,0)=0$, $\alpha(a,1)=1$ and $\alpha(a,n)=a$ for $n\ge 2$ are initial values and $(x\mapsto f(x))^k$ is the k-times composition of the function $x\mapsto f(x)$.
The function $n\mapsto \varphi(n,n,n)$ is not primitive recursive because - informally speaking - it grows too quickly.


These operations are right-bracketed, this does not matter for $\varphi(a,b,1)=ab$ and $\varphi(a,b,2)=a^b$, but for the next higher rank it is important 
$\varphi(a,b,3)=\underbrace{a^\land (a^\land (...(a^\land a)))}\_{b+1\; \text{occurences of}\; a}$ where $a^\land b:=a^b$.


If we would choose left-bracketing the functions would not grow so quickly. The left-bracketed operations would be defined as:


* $\psi(a,b,0) = a+b$
* $\psi(a,b,n+1) = (x\mapsto \psi(x,a,n))^b(\alpha(a,n))$


Again $\psi(a,b,1)=ab$ and $\psi(a,b,2)=a^b$, but here the forth operation would be $\psi(a,b,3)=a^{a^b}$


My question is now whether the left-bracketed operations still grow fast enough for not being primitive recursive, i.e. is $n\mapsto \psi(n,n,n)$ still not primitive recursive?


[1] Ackermann, W. (1928 ). Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann., 99, 118–133.



Left-bracketed Ackermann function also not primitive recursive?
Sorry for reviving this ancient post, but it seemed to me that this question shouldn’t be left unanswered.


It is easy to establish by induction that for $a,b,n\ge2$, the function $\psi(a,b,n)$ is strictly increasing in all three coordinates, and $$\psi(a,b,n)>a,b,n.$$
Then we can show
$$\tag{$\*$}\psi(a,b,n+1)\ge\psi(b,a,n)$$
for $a,b,n\ge2$ by induction on $b$: clearly, $\psi(a,2,n+1)=\psi(\psi(a,a,n),a,n)\ge\psi(2,a,n)$, and going from $b$ to $b+1$, we have
$$\psi(a,b+1,n+1)=\psi(\psi(a,b,n+1),a,n)\ge\psi(\psi(b,a,n),a,n)\ge\psi(b+1,a,n)$$
using monotonicity and $\psi(b,a,n)\ge b+1$.


Thus, by $(\*)$ and monotonicity, we get
$$\psi(a,b,n+2)\ge\bigl(x\mapsto\psi(a,x,n)\bigr)^b(a),$$
which implies
$$\psi(a,b,2n-2)\ge\varphi(a,b,n)$$
for all $a,b,n\ge2$ by induction on $n$. Consequently, $\psi$ (or its diagonal, for that matter) is not bounded by any primitive recursive function.


