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.
Best Answer
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:
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.