Is compare computable?

Consider the procedure compare (p1, p2) where:

Input: source code for procedures p1, and p2.
Output: True if p1 and p2 always produce identical outputs; False otherwise

Is compare (p1, p2) computable or not? Why or why not?

Cans someone expl开发者_Go百科ain what this means?

In general, it is not. The exact task would be to determine if p1 and p2 halt and produce identical outputs. Since it is not computable if p1 and p2 halt (or even one of them), compare is not computable either.

However, if p1 and p2 are constrained to some subset of the set of all computable functions (e.g. functions without recursion, i.e. no loops), compare may well be computable, even in linear time.

It's not computable.

I don't remember the exact reason, but it was something about a special case where you are feeding compare itself into compare which you can use to prove it's not possible to write such a function.