# can we computably list every primitive recursive function?

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 ?

• Instead of saying what you've heard, please describe in details what you are uncertain of, and make sure the title corresponds to your actual question. Mar 21 at 20:25
• "this should only work if we can create an infinite list of every possible primitive recursisve function in a computable way" Why should that be the case? Mar 21 at 22:25
• @Nathaniel if not, then how will you prove that the new function created by diagonalization is also computable ? It can only be computable if the list itself is computable, Don't you think ? Mar 22 at 6:14
• @PålGD I can't directly see how Rice theorem would be helpful here, since it takes into account every possible computable function, and I am talking about only primitive recursive functions... If you think rice theorem proves what I am asking is impossible, can you please show me how.. ? Mar 22 at 6:20
• You can enumerate all primitive functions by using the axioms. Mar 22 at 7:00

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.

• Wow, quite helpful... thanks. Mar 28 at 5:47

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.