I have a question about the standard rules for computing p.r. terms (see below). It seems pretty clear that these rules could be used to define a p.r. operation that evaluates any p.r. term of the form $f_n(n)$. But we know that such an operation does not exist, due to diagonalization arguments. What am I misunderstanding?

  1. Base Functions

\begin{align*} &\text{Zero}(x) \mapsto 0 \\ &\text{Succ}(x) \mapsto x + 1 \\ &P_i^n(x_1, x_2, \ldots, x_n) \mapsto x_i \end{align*}

  1. Composition

\begin{align*} &h_i(x_1, x_2, \ldots, x_n) \mapsto y_i \quad \text{for } i = 1, 2, \ldots, m \\ &g(y_1, y_2, \ldots, y_m) \mapsto z \\ &f(x_1, x_2, \ldots, x_n) = g(h_1(x_1, x_2, \ldots, x_n), \ldots, h_m(x_1, x_2, \ldots, x_n)) \mapsto z \end{align*}

  1. Primitive Recursion

\begin{align*} &f(0, x_1, \ldots, x_n) \mapsto g(x_1, \ldots, x_n) \\ &f(k, x_1, \ldots, x_n) \mapsto y \quad \text{(Assume this has been computed for } k) \\ &h(k, y, x_1, \ldots, x_n) \mapsto z \\ &f(k+1, x_1, \ldots, x_n) \mapsto z \end{align*}

To clarify, I have in mind the followin algorithm.If $phi(n)$ is an expression defining $f_n(n)$, then find the inner most functional expression within $phi(n)$ and compute that as per the above rules. (By inner most, I mean the functional expression embedded in the most parentheses. When there is a tie, you could start with the leftmost one, and then move right.) Then, you take the resulting expression, and repeat the process, until you arrive at a numeral denoting the output of $f_n(n)$

  • 1
    $\begingroup$ Why would that algorithm be primitive recursive? Naively, it looks like an unbounded search. (Also, you would need to compute the term $\phi(n)$ from $n$ but I don’t think that part’s problematic.) $\endgroup$ Commented Jun 22 at 7:00
  • $\begingroup$ I assume you can enumerate the symbols for the various $f_n$, hence, their definitions (in something like PRA). And that enumeration would be p.r. So let $phi(n)$ be the definiens after you have replaced the variable with the numeral for n. That is a finite string so the search for the innermost-leftmost functional expression is not unbounded. $\endgroup$
    – nontology
    Commented Jun 22 at 7:05
  • $\begingroup$ How do you know at the outset how many reductions you are going to have to do though? I would think this looks like: while(not reduced(term)): reduce_one_step(term) $\endgroup$ Commented Jun 22 at 7:12
  • $\begingroup$ I was thinking: for(not_numeral(term)): reduce_one_step(term), where a tally numeral can be identified by whether it begins with '0'. But I suppose the for loop has to be repeated an unknown number of times... $\endgroup$
    – nontology
    Commented Jun 22 at 7:33
  • $\begingroup$ The question here isn't the same, but the answer basically is: math.stackexchange.com/questions/4020853/… $\endgroup$ Commented Jun 22 at 18:45

1 Answer 1


The evaluation function $\sf ev$ s.t. $\mathsf{ev}(i,j) = \varphi_i(j)$ is total recursive given that $\varphi_i(j)$ is primitive recursive and defined.

But, as @spaceisdarkgreen commented, $\sf ev$ is not primitive recursive. Suppose otherwise, then $f(i)= \mathsf{ev}(i,i) + 1$ is also primitive recursive. Then there is an $i$ s.t. $\varphi_i =f$. By standard diagonalization argument, we have $f(i) = \mathsf{ev}(i,i)+1 = \varphi_i (i)+1 = f(i)+1$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .