16
$\begingroup$

The Ackermann function $A(m,n)$ is a binary function on the natural numbers defined by a certain double recursion, famous for exhibiting extremely fast-growing behavior.

One finds various slightly different formulations of the Ackermann function, with slightly different initial conditions. I prefer the following version:

\begin{eqnarray*} A(0,n) &=& n+1 \\ A(m,0) &=& 1, \quad\text{ except for }A(1,0)=2\text{ and }A(2,0)=0\\ A(m+1,n+1) &=& A\bigl(m,A(m+1,n)\bigr). \end{eqnarray*}

I like this version because it has the nice properties that

\begin{eqnarray*} A(0,n) &=& n+1\\ A(1,n) &=& n+2\\ A(2,n) &=& 2n\\ A(3,n) &=& 2^n\\ A(4,n) &=& 2^{2^{\cdot^{\cdot^2}}}{}^{\bigr\}n}\\ \end{eqnarray*}

In this way, the levels of the Ackermann function exhibit increasingly fast-growing behavior.

Each horizontal level of the Ackermann function, the function $A_m(n)=A(m,n)$ considered as a unary function with $m$ fixed, is defined by recursion using the previous level, and consequently all these functions are primitive recursive.

Furthermore, these functions are unbounded in the primitive recursive functions in the sense that every primitive recursive function is eventually bounded by some horizontal level $A_m$ of the Ackermann function. It follows from this that the diagonal of the Ackermann function $n\mapsto A(n,n)$ is not primitive recursive.

My question is about the sections of the Ackermann function taken on the other coordinate, the vertical sections of the Ackerman function, the functions $A^n(m)=A(m,n)$, for fixed $n$.

Question. Are the vertical sections of the Ackermann function $A^n$ each primitive recursive?

I don't expect the answer to depend on which particular version of the Ackermann function one uses, but just in case, let me mention another standard version, which has a smoother definition, which works better in many of the inductive arguments, even though the level functions are not as nice.

\begin{array}{lcl}\operatorname {A} (0,n)&=&n+1\\\operatorname {A} (m+1,0)&=&\operatorname {A} (m,1)\\\operatorname {A} (m+1,n+1)&=&\operatorname {A} (m,\operatorname {A} (m+1,n))\end{array}

$\endgroup$
6
  • $\begingroup$ No, already $A^3$ is not PR. $\endgroup$
    – Wojowu
    Dec 12, 2020 at 11:01
  • $\begingroup$ Great! But can you post a proof? But also, in that case, why do we talk about the diagonal, rather than just $A^3$? $\endgroup$ Dec 12, 2020 at 11:02
  • $\begingroup$ And do you mean $A^3$ for my preferred version, or for the Ackermann–Péter function? $\endgroup$ Dec 12, 2020 at 11:03
  • 1
    $\begingroup$ I will try to write up the proof. I suppose we use the diagonal simply because it is easier to see it is not PR. And I mean your version, in the Ackermann-Peter version already $A^1$ would be not PR. $\endgroup$
    – Wojowu
    Dec 12, 2020 at 11:03
  • 11
    $\begingroup$ We have $A^2(m+1) = A(m+1,2) = A(m,A(m+1,1))$, and $A(m+1,1)\geq m$ is pretty obvious, as is the fact that $A_m$ is increasing, so $A^2(m+1) \geq A(m,m)$, and since $m\mapsto A(m,m)$ outgrows every PR function, so does $A^2$. Did I get something wrong? $\endgroup$
    – Gro-Tsen
    Dec 12, 2020 at 11:22

2 Answers 2

22
$\begingroup$

No, already $A(n,3)$ is not primitive recursive. Let me use the essentially equivalent up-arrow notation: $A(n,m)=2\uparrow^{n-1}m$, and argue why $f(n)=2\uparrow^n 3$ is not PR. I claim $f(2n-2)\geq 2\uparrow^{n+1}n=A(n,n)$. $n\mapsto A(n,n)$ outgrows all $n\mapsto A(m,n)$, so by a classical argument it eventually outgrows all PR functions, and hence so will $f$ after we justify the claim.

It is enough to show that for $m\geq 3$ we have $2\uparrow^n m\geq 2\uparrow^{n-1}(m+1)$. We show this by induction on $m$. Indeed, $2\uparrow^n m=2\uparrow^{n-1}(2\uparrow^n(m-1))$, so it is enough to show $2\uparrow^n(m-1)\geq m+1$. This holds true for $m=3$ as $2\uparrow^n 2=4$ for all $n$, and for larger $m$ we have $2\uparrow^n(m-1)=2\uparrow^{n-1}(2\uparrow^n(m-2))\geq 2\uparrow^{n-1}m\geq m+1$.

Let me note that the bound $f(2n-2)\geq 2\uparrow^{n+1}n$ is far from optimal, in fact it should hold for $f(n+2)$, at least for large enough $n$.

$\endgroup$
20
$\begingroup$

If you don't mind not getting the best possible result, then the proof is very short. Indeed,

$$A(n,4)=A(n-1,A(n,3))$$

so if you can prove that $A(n,3)\geq n-1$ then $A(n,4)\geq A(n-1,n-1)$, which we know doesn't grow primitive-recursively. But $A(n,3)$ grows much more quickly than $n-1$.

$\endgroup$
2
  • 2
    $\begingroup$ Just seen that Gro-Tsen had already made essentially this argument. $\endgroup$
    – gowers
    Dec 12, 2020 at 17:18
  • 2
    $\begingroup$ Thank you very much for this soft answer, which is how I shall prefer to think about it. What I find curious about the situation is that this fact shows the typical emphasis on the diagonal is somewhat misplaced. One proves the horizontal sections are cofinal in PR by induction on the PR definitions, and then a soft argument like this can show that the vertical sections are too fast to be PR, without ever needing to consider the diagonal function specifically. $\endgroup$ Dec 14, 2020 at 10:24

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.