can we computably list every primitive recursive function?

Question

i have seen some articles where they use the diagonalization argument to prove the existence of non-primitive recursive functions. But this should only work if we can create an infinite list of every possible primitive recursisve function in a computable way, like say for eg we should be able to find the output of nth primitive recursive function at the nth input in a computable way. so is there any algorithm which can return any nth input of mth primitive recursive function ?

Answer 1

I'll build on Pål's answer to be a bit more explicit about how we can code PR functions using those operations. First of all, note that we can code any finite sequence of (positive) numbers into a single number such that the $i$'th element of the sequence can be extracted; for instance, this should be doable by mapping the sequence $\{a_1, a_2, \ldots, a_n\}$ to the number $2^{a_1}+2^{a_1+a_2}+2^{a_1+a_2+a_3}+\cdots+2^{\sum_{i=1}^na_i}$. I'll use the standard notation of representing the value of list function (since the specific details of it don't matter) by $\langle a_1, a_2, \ldots, a_n\rangle$.

From here, we do the standard recursive coding steps. More explicitly, we'll label the code of the function $f()$ by $\overline{f}()$. Then we have:

1. The constant function $C_n^k$ is coded by $\overline{C_n^k}=\langle 1, n, k\rangle$.
2. The successor function $S$ is coded by $\overline{S} = \langle2\rangle$.
3. The projection function $P_i^k$ is coded by $\overline{P_i^k}=\langle 3, i, k\rangle$.
4. If the codes of $g_1, g_2, \ldots$ are $\overline{g_1}, \overline{g_2}, \ldots$ and the code of $h$ is $\overline{h}$ then the code of the composition $h(g_1, g_2, \ldots, g_m)$ is $\langle 4, m, k, \overline{h}, \overline{g_1}, \ldots, \overline{g_m}\rangle$, where $k$ is the arity of the $g_i$ (and thus the composite function).
5. If the code of $g$ is $\overline g$ and the code of h is $\overline h$ then the code of the (primitive) recursive applicator is $\overline{\rho(g,h)}= \langle 5, k, \overline{g}, \overline{h}\rangle$, where again $k$ denotes the arity of $g$.

Note that not every natural number necessarily corresponds to a valid function! But given a natural number, we can primitive-recursively determine whether it does code a valid function or not, and if it does we can compute the value of that function given specified inputs. This is enough to make the original proof go through.

Answer 2

The primitive recursive functions can be defined in terms of the following five axioms:

1. Constant function: $C_n^k$ is a $k$-ary function that always returns $n$
2. Successor function: $S$ is a 1-ary function $S(x) \mapsto x+1$
3. Projection function: $P^k_i$ is a $k$-ary function that returns its $i$th argument
4. Composition operator: $h \circ (g_1, \dots, g_m) = h(g_1(\overline x), ..., g_m(\overline x))$ where $\overline x$ is a list of $k$ values
5. Primitive recursive operator: $\rho(g,h)$ takes a $k$-ary function $g$ and a $k+2$-ary function $h$, and essentially runs a (bounded) for loop.

The point is that all these are at most countable infinite and we can enumerate the functions that can be built from these axioms.