# Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function “Abit” primitive recursive?

Example of "Abit": Ack$(2,3)=9=1001_2$ (base 2). Thus Abit(2,3,3)=1
(the leftmost bit of $1001$. The index of the rightmost bit is 0)

Question 1: Is the function "Abit" primitive recursive (PR)?

Let Amod$(x,y,m)=$Ack$(x,y)$ mod $m$. For instance Amod$(3,4,5)=0$ because $125$ mod $5=0$.

Question 2 Is "Amod" primitive recursive?

1. We have: Abit$(x,y,n)=1$ iff Amod$(x,y,2^{n+1})\geq2^n$, so that [Amod is PR] => [Abit is PR]
2. The graph of "Ack" is: Agraph$(x,y,z)=1$ iff Ack$(x,y)=z$, $0$ otherwise. The function "Agraph" is PR.
3. If Abit$(x,y,n)$ is not PR we have an example of a natural (definable by a set of recursive equations) function that is total recursive, not PR, and small (codomain {0,1}). This would be a positive answer to the previous question
Are there natural, small, and total recursive functions that are not primitive recursive?

I apologize if these questions were already discussed,
Armando Matos

• I'm not sure what you mean by "definable by a set of recursive equations" but if you mean that it is definable by a double recursion or multiple recursion like the Ackermann function, then that would imply that it is primitive recursive since it's easy to bound the size of verification tables. – François G. Dorais May 12 '14 at 11:50
• cstheory.stackexchange.com might be a better place to ask this kind of question (if you do so, please link back to this page). – j.p. May 12 '14 at 13:09
• To F. G. Dorais. 1. Yes, your interpretation is ok. 2. How can we bound the tables? Does for instance A(x-1,A(x,y-1))%m depend only on (x-1)%m and A(x,y-1)%m (the args mod m)? Or does it depend on the entire computation? – Armando Matos May 12 '14 at 13:57
• There are many different “Ackermann” functions in the literature (to begin with, the function actually introduced by Ackermann takes three arguments, not two). While they share fundamental properties such as approximate growth rate, the particulars of the definition may well affect the answer to your questions, as the devil is in the detail when it comes to bit fiddling. So, you need to specify exactly what you want. – Emil Jeřábek May 12 '14 at 14:56
• Thanks for your observations! I was thinking in the version A(0,n)=n+1, A(m+1,0)=A(m,1), A(m+1,n+1)=A(m,A(m+1,n)), as used for instance in the wikipedia. I was interested in a version for which the function Abit(m,n,b), the bit b of A(m,n), is not PR. – Armando Matos May 12 '14 at 15:11

The answer may depend on details of the definition of the Ackermann function, of which many variants exist. However, the answer to Question 1 is positive at least for the Péter/Robinson and Friedman variants mentioned in the Wikipedia article. For Friedman, the values of the function are powers of 2 (except for the first row), hence $\mathrm{Abit}(x,y,n)=1$ iff $\mathrm{Ack}(x,y)=2^n$. This is a reduction to the graph of the function, which is known to be primitive recursive. A similar argument works for the Péter/Robinson variant, as for $x\ge3$, $\mathrm{Ack}(x,y)$ has the form $2^z-3$.

EDIT: The function Amod is also primitive recursive for the Péter/Robinson variant, Friedman variant, and the original Ackermann’s function. In fact, one can prove the same for a fairly general class of Ackermann-like functions:

Theorem: Let $A(k,n,p_1,\dots,p_l)\colon\mathbb N^{l+2}\to\mathbb N$ be a function such that there exists a constant $c$ with the following properties:

1. For each $c'\le c$, $A(c',n,\vec p)$ is primitive recursive as a function of $n,\vec p$.

2. $A(k,0,\vec p)$ is primitive recursive, and $A(k,0,\vec p)>0$ for $k>c$.

3. $A(k+1,n+1,\vec p)=A(k,A(k+1,n,\vec p),\vec p)$ for $k\ge c$.

4. For each $\vec p$, the unary function $f(n)=A(c,n,\vec p)$ is strictly increasing, and $f(1)>1$. For all $m>1$, $$\tag{*}n\equiv n'\pmod m\implies f(n)\equiv f(n')\pmod m,$$ and the induced function $\mathbb Z/m\mathbb Z\to\mathbb Z/m\mathbb Z$ is not a permutation with a single $m$-cycle.

Then the function $A(k,n,\vec p)\bmod m$ is primitive recursive.

Note that $(*)$ holds whenever $f(n)$ is an integer polynomial. For example, the Friedman variant satisfies the assumptions with $c=1$, where $A_F(1,n)=2n$. (This is not an $m$-cycle modulo $m$ as it has a fixpoint $0$.) Similarly, for the original Ackermann’s function $A_A(k,n,p)=\varphi(p,n,k)$ we can take $c=1$ with $A_A(1,n,p)=pn$ as long as $p\ge2$. The Péter/Robinson variant is obtained as $A_{PR}(k,n)=A_F(k-1,n+3)-3$ for $k\ge2$.

Proof: In order to ease the notation, we assume $c=0$, and we will suppress the parameters $\vec p$, writing $A_k(n)=A(k,n,\vec p)$. Note that condition 3 then reads $A_{k+1}(n)=A_k^{(n)}(A_{k+1}(0))$.

Since it is (strictly) increasing, $A_0(n)>n$ for $n>0$. The iteration $f^{(n)}(u)$ of an increasing function $f$ satisfying $f(n)>n$ is also increasing, and $f^{(n)}(u)>n$ as long as $u>0$. Thus, all the functions $A_k$ are increasing.

Let $m>0$. If we iterate the function $A_0(n)\bmod m$ on a fixed input $A_1(0)$, we must reach a cycle after at most $m$ steps. Thus, $$\tag{*{*}}x,x'\ge m\land x\equiv x'\pmod{r(m)}\implies A_1(x)\equiv A_1(x')\pmod m,$$ where $r(m)$ is the cycle length. By assumption 4, $r(m)<m$ except for $r(1)=1$.

Using $A_1(x)\ge x$, we can iterate $(**)$ to obtain $$x,x'\ge m\land x\equiv x'\pmod{r^{(n)}(m)}\implies A_1^{(n)}(x)\equiv A_1^{(n)}(x')\pmod m$$ for every $n\ge0$. However, $r^{(n)}(m)=1$ for $n\ge m$ as $r$ is decreasing. Since also $A_1^{(n)}(x)\ge n$, we get $$n\ge2m\implies A_2(n)\equiv A_2(2m)\pmod m,$$ i.e., $A_2$ is eventually constant modulo $m$. Since for $k>2$ the values of $A_k(n)$, $n>0$, form an increasing subsequence of the values of $A_2$, they are also eventually constant mod $m$, and specifically we have $$k\ge 2,n>0,A_k(n)\ge A_2(2m)\implies A_k(n)\equiv A_2(2m)\pmod m.$$ This gives a primitive recursive algorithm to compute $A_k(n)\bmod m$ given $k\ge2$, $n$, $m>0$, and $\vec p$: we compute $A_2(0),\dots,A_2(2m)$ and $A_3(0),\dots,A_k(0)$, and then by induction on $2<k'\le k$, we use it to compute $A_{k'}(1),\dots,A_{k'}(n_{k'})$ where $n_{k'}$ is the last positive number such that $A_{k'}(n_{k'})\le A_2(2m)$ (that is, $A_{k'}(n_{k'})>A_{k'-1}(n_{k'-1})$), if any. Then we either have computed $A_k(n)$ and we can reduce it mod $m$, or the result is $A_2(2m)\bmod m$.

• That's interesting. Let me just make a simple observation: if follows that we can compute, from the right to the left and in a primitive recursive fashion, the successive bits of Ack(x,y); however the whole value of Ack(x,y) can not be primitive recursively computed. This shows that Ack(x,y) is not primitive recursive only because it grows too fast. A similar argument uses Agraph(x,y,z): we can compute in succession A(x,y,0), A(x,y,1)... but there is no primitive recursive way of finding z such that A(x,y,z)=1. – Armando Matos May 12 '14 at 16:14
• That's true, but arguably not particularly special: the same applies to $2^{Ack(x,y)}$. – Geoffrey Irving May 12 '14 at 16:41

This is obvious: since A isn't primitive recursive, Abit and Amod aren't.

• By this reasoning, 2*A is also not primitive recursive, so the functions modulo 2 and the 0th bit of 2*A can't be primitive recursive. Gerhard "So Neither Are Constant Functions?" Paseman, 2018.01.14. – Gerhard Paseman Jan 14 '18 at 17:52