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?

Comments


*

*We have: Abit$(x,y,n)=1$ iff Amod$(x,y,2^{n+1})\geq2^n$,
so that [Amod is PR] => [Abit is PR]

*The graph of "Ack" is: Agraph$(x,y,z)=1$ iff Ack$(x,y)=z$, $0$ otherwise.
The function "Agraph" is PR.

*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
 A: 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:
  
  
*
  
*For each $c'\le c$, $A(c',n,\vec p)$ is primitive recursive as a function of $n,\vec p$.
  
*$A(k,0,\vec p)$ is primitive recursive, and $A(k,0,\vec p)>0$ for $k>c$.
  
*$A(k+1,n+1,\vec p)=A(k,A(k+1,n,\vec p),\vec p)$ for $k\ge c$.
  
*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$.
A: This is obvious: since A isn't primitive recursive, Abit and Amod aren't.
