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.