[plt-scheme] Check for function equality?

[Stephen Bloch]

On Feb 20, 2009, at 10:37, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:

> The set of programs that halts is r.e., because the semi-decision  
> procedure is just running the program! But the set of pairs of  
> equivalent functions is not r.e., and neither is the set of pairs of  
> non-equivalent functions.

If you restrict your attention to total functions, it certainly is:  
for each possible input, run both functions until they stop, and if  
the answers don't match, report that fact.

Even without assuming totality, you can detect any place that the  
functions both terminate and give different answers; what you can't  
detect is places that one terminates and the other doesn't (I think  
that problem is complete for the second level of the arithmetic  
hierarchy, as halting is complete for the first level).

Steve Bloch