3
$\begingroup$

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?

$\endgroup$
6
  • 3
    $\begingroup$ If you can implement a pairing function under these constraints, then you don't lose anything other than convenience. $\endgroup$ Commented Aug 9, 2019 at 4:16
  • 1
    $\begingroup$ Can't you define multiplication by $x \times 0 = 0$ and $x \times Sy = (x \times y) + x$? $\endgroup$
    – Rob Arthan
    Commented Aug 9, 2019 at 15:36
  • $\begingroup$ Oh, of course - somehow I'd convinced myself I needed +y, not +x. Thanks! $\endgroup$
    – ECG
    Commented Aug 9, 2019 at 21:26
  • $\begingroup$ What about predecessor? Is it possible to prove that predecessor is not definable in this framework? $\endgroup$ Commented Aug 10, 2019 at 9:00
  • 2
    $\begingroup$ @Taroccoesbrocco: predecessor is definable, but it's a bit tricky. See A Reduction of the Recursion Scheme by M. D. Gladstone JSL, Vol. 32, No. 4 (1967). Available on JSTOR here $\endgroup$
    – Rob Arthan
    Commented Aug 10, 2019 at 11:33

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .