Computable function that enumerates the primitive recursive functions

Question

I'm trying to construct a computable function $f:\omega^2\to\omega$ such that

• For all $e\in\omega$, $x\mapsto f(e,x)$ is primitive recursive.
• If $g:\omega\to\omega$ is primitive recursive, then there exists $e\in\omega$ such that $f(e,x)=g(x)$ for all $x\in\omega$.

What I've tried so far:

By the normal form theorem there's a primitive recursive unary function $U$, and a trinary recursive relation $T_1$ such that if $f$ is a unary partial recursive function, then it has a code $e$ such that: $$f(x)=U(\mu yT_1(e,x,y))$$

So it seems like there should be a computable relation $Q_1$ that determines if $e$ is a code for a unary partial recursive function, and then we have a computable function $c$ defined by

$$c(e,x)=\begin{cases}U(\mu y(T_1(e,x,y)) &\mbox{if }Q(e)\\0 &\mbox{otherwise}\end{cases}$$

The notes I'm working from codes finite sequences of numbers as follows

$$\langle x_0,\dots,x_n\rangle:=2^{x_0+1}3^{x_1+1}\dots p_n^{x_n+1}$$

And we have primitive recursive functions/predicates like $seq(e)$ that says $e$ codes a sequence, $lth(e)$ that outputs the length of $e$, and $(e)_i$ that outputs the $i$-th number in the sequence coded by $e$.

The partial recursive functions are then coded by

• $\langle 0\rangle$ corresponds to $O$ the zero function
• $\langle 1\rangle$ corresponds to $S$ the successor function
• $\langle 2,n,i\rangle$ ($1\le i\le n$) the projection functions
• $\langle 3,a_1,\dots,a_n,b\rangle$ for the composition $\chi(\psi_1(x)\dots,\psi_n(x))$ where $b$ codes $\chi$, $a_i$ codes $\psi_i$.
• $\langle 4,a,b\rangle$ for primitive recursion from $\chi,\psi$.

And just for completeness

• $\langle 5,a\rangle$ for $\mu$-recursion.

So if $e$ codes a unary primitive recursion function, we have $(e)_1\in\{0,1,2,3,4\}$ and some obvious requirements like $(e)_1=2\implies lth(e)=3\wedge(e)_2=(e)_3=1$.

But then it starts to turn into a mess when I consider composition, because I need $b$ to code an $n$-ary primitive recursive function, so do I need to find a primitive recursive relation that decides if $b$ does so?

So I need $Q_n(e)$ that says $e$ codes an $n$-ary primitive recursive function, so we have $\chi_{Q_n}(0)=0$ for all $n\ge 1$.

But then to define the $Q_n$ it seems like I would need to somehow use all the $Q_n$s simultaneously, which doesn't seem allowable.

And at that point I give up.

Also I've tried searching for R. Péter's construction, but the closest I came was a German version of her book (at least I think that's what it was), but unfortunately I don't speak German so it wasn't very useful to me personally.

So, is my approach completely wrong? If so what should be I trying, if not how do I get around my problem?

Answer 1

You're on the right path with the encoding of the primitive recursive functions. One remark, the $Q_n$s you need should recognize codes for primitive recursive functions, not for partial recursive ones.

On the other hand, you're out for a long trek if you want to define your $f$ from first principles in terms of primitive recursion and minimization. There's gotta be an easier way. However what that easier way is, depends on which tools you have at your disposal at this place in your course (if you're following a course).

If you have the full Church-Turing thesis available, it will generally be sufficient to argue informally that $f$ can be programmed in your favorite computing formalism.

Alternatively, if you at least have some more friendly formalism than raw Turing machines or primitive-recursion-and-minimization proved equivalent to either of those, then most probably it will be easier to prove that your $f$ is expressible there and then appeal to your earlier equivalence result.

As for your technical problems with the $Q$s, note that whether $x=\langle 4,a,b\rangle$ codes for a p.r. function depends on whether $a$ and $b$ which are both strictly smaller than $x$ do. So you can define your $Q$ by ordinary (not primitive) recursion on its argument.

More technically, if you're stuck in a primitive-recursion world, one option would be to define the function $$ K(n) = \langle k_0,k_1,k_2,\ldots,k_n \rangle $$ where $k_i$ is $m\ge 1$ if $i$ defines an $m$-argument primitive recursive function and $0$ if it doesn't define a primitive recursive function at all.

With a bit of elbow grease you can then define a way to find $k_{n+1}$ given $K(n)$ and $n+1$, given the tools to manipulate Gödel numbers it looks like you already have, and therefore define $K$ itself by primitive recursion.

Then your $f(e,x)$ could start by computing $K(e)$ and checking that its last element is $1$.

---

An alternative to representing the $Q_n$s separately would be to simply decide that at each level everything that does not have one of the forms you give special meaning to (including if it starts with $5$), is by definition a code for the zero function -- of whichever many arguments you need it to have.