Enumerating the Primitive Recursive Functions

Question

This paper constructs a general recursive function which enumerates the primitive recursive functions of one variable without repetitions. However, it presupposes a general recursive $\phi(n,a)$ which enumerates the primitive recursive functions with repetitions. It cites Péter 1951 for this functions. However, I cannot find it a good source of the paper, and even if I did, I'm pretty sure its in Hungarian. Also, according to Kleene, $\phi$ can be constructed with a double recursion. How do we construct this function? Or are there any available papers in English that detail this?

Answer 1

We use the notion of p.r. codes - these are ways of encoding a p.r. function by a single number. A p.r. code for a function is basically a description of how to build it up via the primitive recursion "steps." As such, it's a certificate of the function's primitive recursiveness - but more than that, it's a blueprint for evaluating the function since it tells you what operations to perform. A code may have additional "auxiliary" information to simplify things, e.g. it may explicitly indicate the arity of the function for convenience even though that will be redundant.

Here's one approach. For simplicity, I'll write "$\nu_2(x)$" for the largest power of $2$ dividing $x$; the role of $\nu_2$ is to indicate arity (a p.r. code $x$ with $\nu_2(x)=n$ will be a code for an $n$-ary function).

• $1$ is a p.r. code, for the $0$-ary function $\mapsto 0$.

• $2$ is a p.r. code, for the $1$-ary function $x\mapsto x+1$.

• For each $1\le i\le n$, the number $2^n3^i$ is a p.r. code for the $n$-ary projection function onto the $i$th coordinate.

• If $c, d_1,...,d_k$ are p.r. codes, $\nu_2(c)=k$, and for each $1\le i\le k$ we have $\nu_2(d_i)=m$, then $$2^m5^c7^{\prod_{1\le i\le k}p_i^{d_i}}$$ is a p.r. code for the $m$-ary composition of the function named by $c$ with the functions named by the $d_i$s. (Here "$p_i$" denotes the $i$th prime.)

• If $a,b$ are p.r. codes for functions $f,g$ with $\nu_2(a)+2=\nu_2(b)$, then $2^{\nu_2(a)+1}11^a13^b$ is a p.r. code for the unique $(\nu_2(a)+1)$-ary function $h$ satisfying the equations $$h(y, x_1,..., x_{\nu_2(a)})=\begin{cases} f(x_1,...,x_{\nu_2(a)}) & \mbox{ if $y=0$,} \\ g(z, h(z, x_1,..., x_{\nu_2(a)}), x_1,...,x_{\nu(a)}) & \mbox{ if $y=z+1$.}\\ \end{cases}$$

The point, then, is that there are recursive procedures for $(i)$ checking if a given number is in fact a p.r. code and $(ii)$ if so, evaluating the function that p.r. code represents on a given tuple. (Actually $(1)$ is more than we need - we just need to be able to recursively enumerate the p.r. codes - but we might as well go for the stronger result since it's true. A useful fact here will be that codes only get bigger the more rules we apply - to check if $n$ is a code, we just need to check "function constructions" with $\le n$-many steps.)

Obviously the interesting step is $(ii)$, and this is where things get really tedious. One slick approach is the following. It's not too hard to write a machine $M$ with the property that when we feed $e$ and $n$ into $M$, if $e$ is in fact an index for a machine which successfully evaluates all p.r. codes $<n$ on all inputs then $M(e,n)$ is an index for a machine which successfully evaluates all p.r. codes $<n+1$ on all inputs (the point being that the immediate first step of a computation from a p.r. code is to break it into computations from smaller p.r. codes). But then we can from this $M$ build a machine $N$ which evaluates all p.r. codes on all inputs:

• Define a sequence $m_i$ as $m_1=M(0,1)$ (note that anything is an index for a machine which successfully evaluates all p.r. codes $<1$) and $m_{i+1}=M(m_i, i)$.

• Now in order to evaluate a p.r. code $a$ on input $x$, $N$ looks at the machine with index $m_a$.