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 n-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-braced, 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.

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.

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 n-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-braced, 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-bracing the functions would not grow so quickly. The left-braced 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-braced 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.

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 n-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-braced, 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.

We know that for the by the following equations recursively defined operations $\uparrow_n\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$:

• $m \uparrow_1 k = m+k$
• $m \uparrow_{n+1} 1 = m$
• $m \uparrow_{n+1} (k+1) = m\uparrow_n (m \uparrow_{n+1} k)$

the function $n\mapsto n \uparrow_n n$ is not primitive recursive. (the next 2 operations here are as expected $m\uparrow_2 k = mk$, $m\uparrow_3 k = m^k$)

What do we know about the left-braced operations?:

• $m \downarrow_1 k = m+k$
• $m \downarrow_{n+1} 1 = m$
• $m \downarrow_{n+1} (k+1) = (m\downarrow_{n+1} k) \downarrow_n m$

Here again $m\downarrow_2 k=mk$, $m\downarrow_3 k = m^k$ and additionally $m\downarrow_4 k = m^{m^{k-1}}$. Is the function $n\mapsto n\downarrow_n n$ again not primitive recursive?

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 n-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-braced, 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-bracing the functions would not grow so quickly. The left-braced 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-braced 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.