Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
A very complicated computer program could do the same as the simple program that prints "hi" and halts. Just because the program does not explicitly day that is all it is doing, it does not mean this is not what is doing. Similarly, a recursive function with a very complicated description could actually coincide with a simply described p.r. function, and there is no general method to foresee this (by Rice's theorem, as you mentioned). –  Andres Caicedo May 23 '12 at 15:45

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer
    
“there is no decision procedure…” Is there an easy proof of this fact? –  kirelagin Jul 31 at 11:52
    
I think I’ve got a proof. Suppose the set of programs computing PR functions is decidable. Then, given a program q define f_q(x): {q(q); return 1}. f_q computes a PR function (const 1) iff q(q) terminates. This decides the halting problem. –  kirelagin Jul 31 at 12:09

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.

share|improve this answer
    
I should have said (explicitly) that at that noncomputable code of a function the operation yields a nonrecursive function. Well, all this is very informal, but I do think it is interesting -and better goes to the crux of the question than simply remarking that some recursive functions defined using minimization, i.e. not directly defined as primitive recursive, can actually be defined as primitive recursive. –  plm May 23 '12 at 22:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.