# Left-bracketed Ackermann function also not primitive recursive?

The original Ackermann function $\varphi\colon \mathbb{N}\times\mathbb{N}\times\mathbb{N}_0\to \mathbb{N}$ as defined in  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?

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

• May I ask (leaving historical curiosities aside) why you use such a complicated version of the Ackermann function ? The recursion $A(1,n)=n+1,A(k,1)=k+1,A(k,n+1)=A(k-1,A(k,n))$ still defines a function such that $A(n,n)$ is recursive but grows too fast to be primitive recursive. This involves only two variables instead of three, and avoids the explicit use of "powers" of a function as in your definition (although of course, in the end it amounts to the same). Apr 20, 2011 at 20:37
• Correcting my above comment : $A(1,n)=2n$ and $A(k,1)=1$. Apr 20, 2011 at 20:46
• The version you describe is the later by Péter cut down version, which I consider a more technical function, fitting better into the proof of non-primitive recursiveness. The originally by Ackermann given function $\varphi$ is associated with the idea of continuing the sequence of $x+y$, $x\cdot y$, $x^y$ to higher operations which is of broader interest than just in recursion theory. Apr 22, 2011 at 9:07
• I also think the use of function iteration (powers) makes the recursion more comprehensible. You can also write the recursion of the Péter-function that way: $A(k,n)=(x\mapsto A(k-1,x))^{n+1}(1)$, or if we slightly change the indexing $A_k(x)=A(k,x)$ then we can write $A_{k}(n)=A_{k-1}^{n+1}(1)$. Unfortunately the lack of one variable does not allow us to distinguish a left- and right-bracketed version of the Péter-function. PS: I use $A(0,n) = n+1$ and $A(k,0)=A(k-1,1)$. Apr 22, 2011 at 9:17

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.