[plt-scheme] Check for function equality?

Wow. Seeing these responses for the first time is like waking up Christmas
morning and finding your stocking stuffed with all kinds of goodies :).
I would never have imagined that a question with such limited aims would
have elicited such a variety of thoughtful and interesting posts.  My
thanks, and apologies for not acknowledging this sooner.

I believe I may have brushed up against the "halting problem" in university
philosophy courses.  In this context, concepts originating in mathematics or
logic weren't explained or even discussed with any seriousness, but instead
were typically used as arrows in the quivers of warring epistemologists
launching broadsides in the mind vs. matter war, much in the same manner and
spirit that philosophers in the 60's marshaled the Heisenberg Principle
against human determinism and in favor of "free will" (cue eye rolling). The
result was precisely as intended, confirming the prejudice in liberal arts
students like myself against anything with a mathematical flavor, and
discouraging any real thought on the subject of these problems.

While leads me to a short aside: in my opinion, there is more than one path
from hell to paradise. To extend the Biblical metaphor a bit, if you want to
be a fisher of men, try casting your lines into any university Continental
Philosophy department.  There you will find a handful of serious students
searching for a discipline, but whose minds are completely absorbed in the
task of untangling the mystical pronouncements of modern thinkers like
Heidegger, Derrida, Foucault, etc. It is doubtful that at the time I would
have had the maturity, as a student of these mystics, to appreciate what is
offered by HtDP, but surely there are some out there who would welcome it as
a bracing blast of fresh air.  Low hanging fruit indeed, and badly in need
of the disciplined approach to analytical thinking developed by HtDP.

Robby, I am quite excited to take up the problem of halts? and will do so as
soon as I get home from work today.

Quick note of qualification. I shouldn't bash on "university philosophy"
courses in general.  I eschewed courses in logic etc. in favor of
metaphysics.  I'm sure there are a lot of great logic courses out there in
phil. departments which approach these issues with the detail and depth they
deserve.  By the way, has anyone out there used / heard of "Tarski's World."
 It a logic study program.  I was thinking of taking it up with a friend.

Thanks again!

Dave Yrueta







On Fri, Feb 20, 2009 at 5:01 PM, Stephen Bloch <sbloch at adelphi.edu> wrote:

> 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
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20090221/000884b0/attachment.html>