[plt-scheme] Check for function equality?

On Thu, Feb 19, 2009 at 4:43 PM, dave yrueta <dyrueta at gmail.com> wrote:
> Hi All --
>
> Is there a Scheme function similar to "check-expect" that tests for
> equality between functions?
>

Some of my students (first year) asked the same question. As you may
imagine by the answers you received so far, it is a tough question to
answer. If you are a student that has not taken a course in automata
theory, I happily suggest you do before trying to tackle your
question. :-) If you are familiar with Turing Machines, then you know
that the Halting Problem is unsolvable and you should be able to
answer your question by reducing the Halting Problem to your problem.
Assume you have a Turing Machine that can answer your question
reliably. Show that if such a Turing Machine exists then you can solve
the Halting Problem. Since we know that the Halting Problem is
unsolvable, then that hypothetical Turing Machine that solves your
problem can not exist. Q.E.D. ;-)

The catch, of course, is the assumption that Turing Machines can be
programmed to solve any solvable problem. Search for Church's Thesis
for more details on that assumption.

Others have suggested using theorem provers. This is also something
that can lead you down an enlightening path. :-)

-- 

Cheers,

Marco