0

Show that for every $x \in \mathbb{N}$ the function $A_x(y) = A(x,y)$ is primitive recursive, with $A(x,y): \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ being the Ackermann function

I need some initial advice how to attack this problem. Since the Ackermann function is known to be not primitive recursive, I think the problem wants me the show that it is primitive recursive for every $n$, with $y$ staying unchanged? My initial thought was to define $A(x+1,y)$ and $A(x,0$) and show that each are primitive recursive.

kklaw
  • 301
  • 1
  • 9
  • You should have a theorem that the composition of primitive recursive functions is primitive recursive. For a given $x$ you need to use that $x$ times. The reason the whole function is not primitive recursive is that you don't know how large $x$ can be. – Ross Millikan Feb 01 '22 at 14:49
  • That is correct. The important thing is that primitive recursive functions can have bounded loops-ones that you can set an upper bound to the number of cycles based on the input but not unbounded loops. The full Ackermann function takes an unbounded loop, but for each $x$ the loop is bounded. – Ross Millikan Feb 01 '22 at 16:07
  • So is $x \in \mathbb{N}$ actually my bound and I need to show via induction that for that bound the Ackermannfunction would be primitiv recursive? – kklaw Feb 01 '22 at 16:31
  • Yes. You can show it for $x=0$ or $x=1$ as a base case from the definition, then argue that since $A_{x+1}$ is defined in terms of $A_x$ it is primitive recursive, too. – Ross Millikan Feb 01 '22 at 21:14
  • I actually tried that, but reached a point where $A_{x+1}(y) = A(x+1,y)$, however, $A(x+1,y)$ is not defined by the Ackermann function. I have tried using $A(x+1,y) = A(x,A(x+1,y-1))$ argueing, that at some point $y$ reaches $0$ and then we have the case that $A(x+1,0) = A(x,1)$ which is primitive recursive due to the Induction Hypothesis, but I doubt its correct – kklaw Feb 01 '22 at 21:17
  • That is the right approach. You actually have two inductions, one on $x$ and one on $y$. As you say, for a given $x$ you have $A(x,0)$ is pr, then you induct on the second argument to show that $A(x,y)$ is pr for all $y$. Now you can go to $x+1$. – Ross Millikan Feb 01 '22 at 22:15
  • Does induct on two arguments mean to have 2 hypothesis and 2 base cases? I have not seen or used this technique before. – kklaw Feb 02 '22 at 05:05
  • Yes. You are trying to prove $\forall x (\forall y (P(x,y))$. The order you do things depends on what you are trying to prove. I believe it is easy to turn $A_0(y), A_1(y), A_2(y)$ into formulas you know are pr. They are something like $y+1, 2y+3,2^y+3$. Now you assume $A_x(y)$ is pr. You can show $A_{x+1}(0)$ is pr, then induct on $y$ to show $A_{x+1}(y)$ is pr. You need the induction on $y$ because $A_{x+1}(y)$ depends on $A_{x+1}(y-1)$ so you need to know that is pr to prove $A_{x+1}(y)$ is pr. It is like nested loops in a program. – Ross Millikan Feb 02 '22 at 05:23

0 Answers0