11
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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). $\endgroup$ Apr 20, 2011 at 20:37
  • 1
    $\begingroup$ Correcting my above comment : $A(1,n)=2n$ and $A(k,1)=1$. $\endgroup$ Apr 20, 2011 at 20:46
  • $\begingroup$ 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. $\endgroup$
    – bo198214
    Apr 22, 2011 at 9:07
  • $\begingroup$ 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)$. $\endgroup$
    – bo198214
    Apr 22, 2011 at 9:17

1 Answer 1

8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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