Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
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). –  Ewan Delanoy Apr 20 '11 at 20:37
Correcting my above comment : $A(1,n)=2n$ and $A(k,1)=1$. –  Ewan Delanoy Apr 20 '11 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. –  bo198214 Apr 22 '11 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)$. –  bo198214 Apr 22 '11 at 9:17
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.