There are effectively computable numerical functions which aren’t prim

[robertjford80]

This is from Peter Smith's Gödel without tears.

Theorem 21 There are effectively computable numerical functions which aren’t primitive recursive.

Proof The set of p.r. functions is effectively enumerable. That is to say, there is an effective way of numbering off functions f0, f1, f2, ..., such that each of the fi is p.r., and each p.r. function appears somewhere on the list.
This holds because, by definition, every p.r. function has a ‘recipe’ in which it is defined by recursion or composition from other functions which are defined by recursion or composition from other functions which are defined ...ultimately in terms of some primitive starter functions.

see attachment


So choose some standard formal specification language for representing these recipes. Then we can effectively generate ‘in alphabetical order’ all possible strings of symbols from this language; and as we go along, we select the strings that obey the rules for being a recipe for a p.r. function. That generates a list of recipes which effectively enumerates the p.r. functions, repetitions allowed.

Now consider our table. Down the table we list off the p.r. functions f0, f1, f2, ... An individual row then gives the values of fn for each argument. Let’s define the corresponding diagonal function, by putting δ(n) = fn(n) + 1.

To compute δ(n), we just run our effective enumeration of the recipes for p.r. functions until we get to the recipe for fn. We follow the instructions in that recipe to evaluate that function for the argument n. We then add one. Each step is entirely mechanical. So our diagonal function is effectively computable, using a step-by-step algorithmic procedure.

By construction, however, the function δ can’t be primitive recursive. For suppose otherwise. Then δ must appear somewhere in the enumeration of p.r. functions, i.e. be the function fd for some index number d.

I don't agree with this.
If it appears in the list of p.r. functions then it is p.r. I don't see why he thinks that if x is in the list of p.r. functions then it is not p.r.

But now ask what the value of δ(d) is. By hypothesis, the function δ is none other than the function fd, so δ(d) = fd(d). But by the initial definition of the diagonal function, δ(d) = fd (d) + 1. Contradiction.
So we have ‘diagonalized out’ of the class of p.r. functions to get a new function δ which is effectively computable but not primitive recursive.

 

[jgens]

I don't agree with this.
If it appears in the list of p.r. functions then it is p.r. I don't see why he thinks that if x is in the list of p.r. functions then it is not p.r.

This is just a standard diagonal argument. It works by saying "Assuming δ were on the list we reach a contradiction. The only other possibility being δ not on the list the desired conclusion follows." For whatever reason this type of argument seems to give some people trouble. You might be one of those people.

Edit: If you are one of those people, then my advice is first use the forum software to search for threads about the Cantor diagonalization argument, because it has been discussed at length on the forum before. After reading those threads, if you still have problems, then come back and ask specific questions.