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?
Best Answer
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)$.