[BULK] Re: [plt-scheme] OT: not the halting problem, but what is it?

Sometimes in class I've preceded the discussion of the halting problem with the question "Do all well-defined functions have programs that compute them?"  We then show that there are countably many programs in any "reasonable" language (finite strings over a finite alphabet), and uncountably many functions, so ALMOST ALL functions are incapable of being computed by any program.  But that doesn't help you put your fingers on one, so then we get into the Halting Problem.

In fact, I'm scheduled to do the undecidability of HP in one of my classes tomorrow; this reminds me that I should do the cardinality argument first.


Stephen Bloch
sbloch at adelphi.edu