Primitive recursive functions, Recursive functions and recursive set

Question

I'm trying to understand basic computability notions, and I'm a bit confused concerning the following questions : Is the set of (Gödel numbers of) partial recursive functions recursive ? Is the set of (Godel numbers of) primitive recursive functions recursive ?

Let me explain why I'm puzzled : As far as I have heard about computability theory, the answer to the first question is yes, and the answer to the second one is no (and this is a direct consequence from Rice's Theorem, if I understand it well). But it seems to me that the argument I found to answer yes to the first question can also be used to answer yes to the second question. This argument is the following :

Let F be the set of all partial recursive functions. For every element of this set, there is a corresponding program in a Turing-complete programming language, and a Gödel number can be associated with this program. So we can now consider the set E of all Gödel numbers of partial recursive functions. This set is recursive, because for any integer n, we can easily obtain the strings of characters that it encodes ; then, if these strings are syntactically well-formed, n encodes a program, thus a partial recursive function, so it belongs to E ; on the other hand, if these strings are not syntactically well-formed, n doesn't belong to E. Since the question of whether a strings of characters is well-formed or not is decidable, the set E is therefore recursive.

This is the argument I read, or at least this is the way I understand it. However, if this argument is valid, then it seems to me that we can built a similar argument concerning the set of primitive recursive functions : given a programming langage and a Gödel numbering of all possible strings of characters, for every integer n, we can determine if the strings of characters it encodes : 1) is syntactically well-formed 2) is a program that can be expressed only with projections, constants, successor function, composition and primitive recursion.

It seems to me that there exist decidable procedures for both 1) and 2), thus making the set of Gödel numberings of primitive recursive functions recursive, which is obviously wrong, given Rice's theorem. Could you please tell me where is the flaw in the argument ? I can only see two possible answers : either there is no algorithm which can tell us that a given program can't be expressed with other programs corresponding to projections, constants, successor, composition or primitive recursion (but in that case, I don't really see why, since it seems to me that there are decidable procedures to recognize all of these operations), or either the first argument presented above is wrong (and in that case, how do we prove that the set of Gödel numbers of partial recursive functions is recursive ?)

Thank you for your attention and for your forthcoming answers.

Answer 1

The trouble is that there could be a program that happens to compute a primitive recursive function, but is not literally written with the limited resources of primitive recursion.

Here is an example. Let $f(n)$ be an arbitrary primitive recursive function. Create a function $h$ that does the following:

• Given input $n$, search for a pair of twin primes large than $n$. In other words, search for primes $p,q$ with $n < p$ and $q= p+2$.
• If that search does find a pair of twin primes larger than $n$, return $f(n)$.

This function $h$ is computable. If there are infinitely many pairs of twin primes, then the function $h$ is the same as $f$, and so is primitive recursive. Otherwise, at some point the function $h$ becomes undefined because the searches never terminate. In the latter case, $h$ is not primitive recursive because it is not even total.

How would you determine based on the algorithm above whether $h$ is primitive recursive? That determination would allow us to tell whether there are infinitely many twin primes, which is a famous open question.

The moral is that a particular index might happen to compute a primitive recursive function even though it does not literally appear to be a primitive recursive function. As you say, Rice's theorem gives a proof that the set of indices that happen to compute primitive recursive functions is not decidable.

Answer 2

There certainly are decision procedures to recognize projections, constant functions, successor, and so on. However, there is no decision procedure to recognize whether a program that uses other procedures, such as $\mu$-recursion (unbounded search) can be replaced by a program that uses only the above procedures.

Remark: We can separately assign indices to primitive recursive descriptions. This is useful for producing, by a diagonalization argument, a computable function which is not primitive recursive.

Answer 3

There is a subtlety that primitive recursive functions written using only primitive recursion can be recognized, "checking syntax". So depending on your interpretation of both questions, question 2 may be answered yes or no.

Similarly question 1 may be answered yes or no, depending on what you call code, "Gödel number", of a recursive function.

If you add an operation on recursive functions, coded in some way compatible with your existing codes, that does nothing to all but one noncomputable (code of a) function (this is possible), then you could not recognized partial recursive functions among that greater set of Gödel numbers. You could still recognize the functions that do not use that new operation, but one of the functions using the new operation would not be recursive and it would not be possible to decide which, with any Turing machine.