# How to prove that this function is primitive recursive?

How can I solve the following problem:

Let $f, \pi, g$ accept one, two and three arguments respectively. If you know that $f, \pi, g$ are primitive recursive functions prove that $h$ defined as: \begin{align*} h(0, y) &\simeq f(y) \\ h(x + 1, y) &\simeq g(x, y, h(x, \pi(x, y))) \end{align*} is also primitive recursive function.

The definition of primitive recursion I know is: \begin{align*} h(\bar{x}, 0) &\simeq f(\bar{x}) \\ h(\bar{x}, y + 1) &\simeq g(\bar{x}, y, h(\bar{x}, y)) \end{align*}

-
Identical problem posted to MO, mathoverflow.net/questions/81757/… I recommend reading what's posted there before answering here. – Gerry Myerson Nov 27 '11 at 5:23
This question might have been perfect for the upcoming Computer Science Stack Exchange. So, if you like to have a place for questions like this one, please go ahead and help this proposal to take off! – Raphael Dec 3 '11 at 17:31

## 2 Answers

It may seem silly to post a second answer to a question that seems no longer to interest anybody, not even the original poster, but I recently realised that for the problem as stated, one can do considerably better than my previous answer. Also this question seems to be more important in the development of primitive recursive functions than it looked to me at first, since a solution allows a value to be built up in one argument while performing primitive recursion on another. For instance, if one wants to encode lists of numbers by repeated pairing as in LISP, and one wants to define a function appending a number $x$ at the end of an $n$-element list $l$, this can be specified as \begin{align} \mathit{append}(0,l,x) &= \mathit{cons}(x,0)\\ \mathit{append}(n+1,l,x) &= \mathit{cons}(\mathit{head}(l),\mathit{append}(n,\mathit{tail}(l),x))\\ \end{align} where $0$ encodes the empty list; we find our non-primitive recursion schema with $\mathit{tail}$ in the role of $\pi$. Thus it seems relevant to have a method for solving this schema that does not depend on encoding sequences into numbers.

So here is a solution that does not use encoding. Define $h$ using auxiliary functions $P$ and $G$ of three arguments each, satisfying the following specifications that match the basic primitive recursive schema: \begin{align} P(n,x,0)&=x\\ P(n,x,i+1)&=\pi(n-(i+1),P(n,x,i)) \\ G(n,x,0)&=f(P(n,x,n)) \\ G(n,x,i+1)&=g(i,P(n,x,n-(i+1)),G(n,x,i)) \\ h(n,x) &= G(n,x,n) \\ \end{align} The intended effect of these definitions is \begin{align} P(n,x,n-i) &= \pi(i,\pi(i+1(\ldots,\pi(n-1,x)\ldots)) \quad\text{and}\\ G(n,x,i) &= g(i-1,P(n,x,n-i),g(i-2,P(n,x,n-i+1),g(\ldots \\ & \qquad\qquad\qquad\qquad\qquad\qquad g(0,P(n,x,n-1),y)\ldots))) \quad\text{where}\\ y &= f(P(n,x,n)) = f(\pi(0,\pi(1,\ldots,\pi(n-1,x)\ldots))), \\ \end{align} and $h(n,x) = G(n,x,n)$ can be seen to give the desired expansion.

To prove formally that the above equations solve the required recursive relation for $h$, one proves successively

Lemma For all $n,i\in\mathbf N$ one has $P(n+1,x,i+1)=P(n,\pi(n,x),i)$,

by induction on $i$, and then

Lemma For all $n,i\in\mathbf N$ one has $G(n+1,x,i)=G(n,\pi(n,x),i)$,

by induction on $i$. Both proofs are straightforward rewriting using the defintions and the induction hypothesis. Finally for $h$ one has $$h(0,x) = G(0,x,0) = f(P(0,x,0)) = f(x)$$ and \begin{align} h(n+1,x) &= G(n+1,x,n+1) \\ &= g(n,P(n+1,x,0),G(n+1,x,n)) \\ &= g(n,x,G(n+1,x,n)) \\ &= g(n,x,G(n,\pi(n,x),n)) \\ &= g(n,x,h(n,\pi(n,x))) \\ \end{align} as desired.

-

I came across this question because I wanted to prove something very similar myself (while teaching a course on computability, so this is not homework for me!). Unfortunately the question was posed in such a way that almost nobody seems to have understood the real issue, and in particular I found no appropriate reply here or at MathOverflow. So I'll try to give my best shot at it, but I would much like to learn a simpler answer (given that it was homework, maybe the OP learned a solution by now?).

So firstly, the difficulty is that while the basic primitive recursion schema allows passing on additional parameters that are not object of the recursion ($\bar x$ in the text of the question) unchanged, the question asks what to do when this parameter is modified by the application of $\pi$. That this is is not in general innocent can be shown by the Ackermann function, which operates by a similar modification of its non-recursion parameter, and which is not primitive recursive (of course the modification is here in terms of the Ackermann function itself while in the question $\pi$ must be primitive recursive, so we may still hope for a positive answer).

I'll first assume that $\pi$ satisfies $\pi(x,y)\leq y$ for all $x,y$, so that the recursion relations only decreases the additional parameter $y$. In that case one has the following solution, somewhat similar to how course-of-values recursion is handled: define first another function $H$ of two arguments by $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$, the encoding of the indicated list into a single number; although apparently $H$ is more complicated than $h$, can be defined more directly by primitive recursion. Indeed what is needed is a primitive recursive function $G$ to compute $H(x+1,y)=\left<h(x+1,0),\ldots,h(x+1,y)\right>$ given the values $x$, $y$, and $H(x,y)=\left<h(x,0),\ldots,h(x,y)\right>$. It should return a list with final component $h(x+1,y)=g(x,y,h(x,\pi(x,y)))$ where $h(x,\pi(x,y))$ is one of the components of $H(x,y)$ by the assumption $\pi(x,y)\leq y$. This component can be computed from $x,y,H(x,y)$ by a primitive recursive function, say $G_0(x,y,z)$ with $z$ taken to be $H(x,y)$. Since the only thing $G_0$ needs to do with the list $z$ is select a component from it, we may assume that it returns the same value whenever $z$ is replaced by a longer list containing $z$ as prefix. Now we can define $G$ primitive recursively by \begin{align*} G(x,0,z) &= \left< G_0(x,0,z) \right> \\ G(x,y+1,z) &= \mathit{append}(G(x,y,z),G_0(x,y+1,z)) \end{align*} where $\mathit{append}$ adds an element to the list encoded as its first argument. (Note how we avoided having to modify $z$ in the recurrence for $G$, as this would have got us into a chicken-and-egg situation.) We can now define $H(x,y)$ by primitive recursion on $x$ using $G$ (I leave computing $H(0,y)$ as an exercise), and finally $h(x,y)$ by taking the final element of the list encoded by $H(x,y)$.

(Another more brute-force approach to this case is to define $h'(z)$ by $h'(\langle x,y\rangle)=h(x,y)$ for an encoding $\langle x,y\rangle$ of the pair $(x,y)$, which encoding may be taken to be bijective (every $z$ encodes a pair) and monotonic (increasing $x$ or $y$ always increases the code $\langle x,y\rangle$; this is true for any reasonable encoding). Then since $\langle x+1,y\rangle > \langle x, \pi(x,y)\rangle$, the recurrence relation that $h$ must satisfy leads to a course-of-values recursion for $h'$, which we know how to handle.)

Now most primitive recursive functions $\pi$ of two arguments do of course not satisfy $\pi(x,y)\leq y$ for all $x,y$, and if not the above methods do not work. However, increase in the non-recursive argument does not form a real obstruction to the computation of $h$, since for each pair $(x+1,y)$ we can predict (using $\pi$) how many values $(x,y')$ we need to compute $f$ for first, and so on for decreasing $x$. So intuitively we can compute $h(x,y)$ by computing successive "rows" (i.e., with fixed $x$) up to a point computable in advance. (This is unlike for the Ackermann function, where each row needs to be developed only to a finite extent, but not predictable until you already know the Ackermann function itself.)

To handle the general case, I first reduce to the case that actually $\pi(x,y)\geq y$ for all $x,y$ and also that $\pi(x,y)$ is monotonic in $y$, while at the same time generalising to the case that $g$ depends (apart from on $x$ and $y$) not only on the value $h(x,\pi(x,y))$, but on the entire (encoded) row $\left<h(x,0),\ldots,h(x,\pi(x,y))\right>$; as we have seen this generalisation does not complicate matters essentially. To obtain the reduction, replace $\pi$ by $\pi'$ defined as $\pi'(x,y)=\mathrm{max}(y,\pi(x,0),\ldots,\pi(x,y))$ if necessary. Now the feature that allows predicting how much values need to be pre-computed, is that for given $x,y$ the final value $l(x,y)$ of the sequence $y$, $\pi(x-1,y)$, $\pi(x-2,\pi(x-1,y))$, ... $\pi(0,\pi(1,\ldots\pi(x-1,y)\ldots))=l(x,y)$ of maximal $y$-values needed respectively for $x$, $x-1$, $x-2$, ..., $0$ can be computed primitive-recursively. Indeed this value is given by $l(x,y)=L(x,x,y)$ where $L$ satisfies \begin{align*} L(0,x,y) &= y, \\ L(i+1,x,y) &= \pi(x-i,L(i,x,y)). \end{align*} Note that by our assumption on $\pi$, the function $l$ is also monotonic in $y$ and satisfies $l(x,y)\geq y$ for all $x,y$. Moreover $l(x+1,y)=l(x,\pi(x,y))$ by definition of $l$.

Now my idea is to define a different function $H(x,z)$ to help define $h$, and which encodes the list of values $h(x,y)$ for all $y$ with $l(x,y)\leq z$. The function $h$ can then be defined by taking $h(x,y)$ to be the value in the list $H(x,l(x,y))$ at index $y$, which is guaranteed to exist (and propbably the last value on the list). The point of $H$ is that, by what we know about $l$, the list encoded by $H(x,z)$ is finite, and $H(x,z)$ contains all previous values $h(x,y)$ that one needs to know to compute the (in general much fewer) values encoded in the list $H(x+1,z)$. So it should be possible to define $H$ by primitive recursion on $x$, with $z$ as an unchanging second argument. I'm a bit tried of giving details though (and I'm sure the reader is as well) so I'll stop here.

-
I thought you might find this article interesting. It is in no way a simpler proof. The statement is a vast generalization of this one, yet a special case of nested recursion. – Student Dec 2 '13 at 18:35