# Why doesn't this diagonal argument work?

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)$$

• 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.) Commented Jun 22 at 7:00
• 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. Commented Jun 22 at 7:05
• 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) Commented Jun 22 at 7:12
• 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... Commented Jun 22 at 7:33
• The question here isn't the same, but the answer basically is: math.stackexchange.com/questions/4020853/… Commented Jun 22 at 18:45

## 1 Answer

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$$.