Wow. Seeing these responses for the first time is like waking up Christmas morning and finding your stocking stuffed with all kinds of goodies :). <div><br></div><div>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. </div>
<div><br></div><div>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. </div>
<div><br></div><div>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. </div>
<div><br></div><div>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. </div><div><br></div><div>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. </div>
<div><br></div><div>Thanks again!</div><div><br></div><div>Dave Yrueta</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br><br><div class="gmail_quote">On Fri, Feb 20, 2009 at 5:01 PM, Stephen Bloch <span dir="ltr"><<a href="mailto:sbloch@adelphi.edu">sbloch@adelphi.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="Ih2E3d">On Feb 20, 2009, at 10:37, Prabhakar Ragde <<a href="mailto:plragde@uwaterloo.ca" target="_blank">plragde@uwaterloo.ca</a>> wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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.<br>
</blockquote>
<br></div>
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.<br>
<br>
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).<br>
<br>
Steve Bloch<div><div></div><div class="Wj3C7c"><br>
_________________________________________________<br>
For list-related administrative tasks:<br>
<a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target="_blank">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a><br>
</div></div></blockquote></div><br></div>