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 ?

  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Mar 21 at 20:25
  • 1
    $\begingroup$ "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? $\endgroup$
    – Nathaniel
    Mar 21 at 22:25
  • $\begingroup$ @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 ? $\endgroup$ Mar 22 at 6:14
  • $\begingroup$ @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.. ? $\endgroup$ Mar 22 at 6:20
  • 4
    $\begingroup$ You can enumerate all primitive functions by using the axioms. $\endgroup$
    – Pål GD
    Mar 22 at 7:00

2 Answers 2


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.

  • $\begingroup$ Wow, quite helpful... thanks. $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.