Restricted definition of primitive recursive function I'm reading Peter Smith's introduction to Gödel's Theorems. He defines a primitive recursive (PR) function as:


*

*Zero, projection, successor functions

*Closed under composition

*Closed under primitive recursion, defined as


$$f(x_1, ..., x_n, Sy) = g(x_1, ..., x_n, y, f(x_1, ..., x_n, y))$$
I was wondering what the class of functions is if you restrict this to not use y:
$$f(x_1, ..., x_n, Sy) = g(x_1, ..., x_n, f(x_1, ..., x_n, y))$$
This seems like it should be more restrictive (I can't obviously get predecessor from this, but I can get multiplication), but I can't prove it.
What family of functions do you get from this?
 A: Good question! This kind of recursion was considered by R. Robinson in Primitive Recursive Functions Bull. AMS, vol 53 (1947) pp. 925-942 (available here). Robinson called your restricted recursion scheme "pure recursion". The functions $x+y$, $xy$ and $x^y$ are all definable by pure recursion and hence so is the very handy function $0^x$, which is the characteristic function of the set $\{0\}$ (or $\{ n \mid n > 0\}$ depending on your conventions).
Robinson observed that if you can give pure recursive definitions of a pairing function $\langle, \rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ and projection functions $\lambda, \rho : \mathbb{N} \to \mathbb{N}$ such that:
$$
\begin{align*}
\lambda(\langle x, y\rangle) &=x \\
\rho(\langle x, y\rangle) &=y
\end{align*}
$$
then pure recursion is equivalent to unrestricted primitive recursion.
(The notation here is mine, not Robinson's.)
To see this (omitting the parameters $x_1, \ldots, x_n$), if we want
to define $f$ such that:
$$
\begin{align*}
f(0)&= h \\
f(S(y)) &= g(y, f(y))
\end{align*}
$$
we can define $f'$ by the pure recursion scheme:
$$
\begin{align*}
f'(0)&= \langle 0, h \rangle\\
f'(S(y)) &= \langle S(\lambda(f'(y))), g(\lambda(f'(y)), \rho(f'(y)))\rangle
\end{align*}
$$
and then put $f(x) = \rho(f'(x))$.
Robinson proposed the following definitions of the pairing and projection functions.
$$
\begin{align*}
\langle x, y \rangle &= (x + y)^2 + x\\
\lambda(x) &= x - \lfloor \sqrt{x} \rfloor^2 \\
\rho(x) &= \lfloor \sqrt{x} \rfloor - \lambda(x)
\end{align*}
$$
The definition of $\langle,\rangle$ can be obtained by composing addition and multiplication and so it is pure recursive.
Robinson noted that $\lfloor\sqrt{x}\rfloor$ is definable by the pure recursion scheme:
$$
\begin{align*}
\lfloor \sqrt{0} \rfloor &= 0 \\
\lfloor \sqrt{S(y)} \rfloor &= \lfloor \sqrt{y} \rfloor + 0^{(S(\lfloor \sqrt{y} \rfloor))^2 - S(y)}
\end{align*}
$$
(the exponent $(S(\lfloor \sqrt{y} \rfloor))^2 - S(y)$ here is $0$ iff
$S(y)$ is a perfect square, so we add $1$ in that case and $0$ otherwise).
Subtraction $x - y$ (for $x \ge y$) can be defined by the following
pure recursion scheme using the predecessor function $P$.
$$
\begin{align*}
x - 0 &= x\\
x - S(y) &= P(x - y)
\end{align*}
$$
Thus pure recursion is equivalent to unrestricted primitive recursion iff
$P$ can be defined by pure recursion. This was subsequently proved by M. D. Gladstone in
A Reduction of the Recursion Scheme JSL, Vol. 32, No. 4 (1967) pp. 505-508 (available here).
The key to Gladstone's proof is a pure recursive definition
of a function $C(x, y)$ such that $C(x, y) = 0$ iff $x \le y$.
Using, this Gladstone defines a function $f$ by
$$
\begin{align*}
f(0, y) &= y \\
f(S(x), y)&= \left\{
\begin{array}{l}
0\mbox{, if $C(y, f(x, y)) = 0$}\\
f(x, y) +1 \mbox{, otherwise.}
\end{array}
\right.
\end{align*}
$$
and then $P(x) = f(x, x)$. (To see this prove by induction on $x$ that
for $1 \le x \le y$, $f(x, y) = P(x)$.) I refer you to Gladstone's short and clear paper for the clever technique he uses to define $C(x, y)$.
