Re: new to extropy:question

Dan Clemmensen (
Wed, 04 Nov 1998 19:46:11 -0500

Michael Fitzgerald wrote:
> John Clark wrote:
> > I wrote about that and some other stuff in my dialog "Waiting For Zed"
> > that was on
> > Extropy Online, this is part of it.
> > ===================================
> Thanks John,
> I was starting to worry that perhaps my question was too dumb to attract
> an answer from the group -which in turn caused me to doubt whether I was
> being realistic in hanging in here.
> Your response, which I must admit, has not left me entirely satisfied
> that I understand the problem any better, has at least reassured me, and
> encourages me to hang in.
Michael, there are entire one-semester college courses devoted to the Church-Turing theorm or one of its relatives. I thought John's description was wonderfully concise. Your question was basically equivalent to one of the "grand-slam" mathematical questions asked by Hilbert (THE grand old man of Mathematics of his time) in 1900, and finally answered by Church in 1936. The history of mathematics of the early twentieth century is mostly about answering the Hilbert questions. Turing's reformulation is a great deal more tractable, but that doesn't make it simple. The central argument depends on a "Cantor diagonalization", which is the really pretty step in the middle described by John. This trick get re-used a lot when proving that certain sets are not countable (i.e., are not "aleph-sub-zero", etc.) This shows up a lot in complexity theory and of course in questions of decidabilty and computability.

If you can ask the correct question and then get basically the distillation of an upper-divison college course as a answer, and then understand the answer to at least some extent, I'd say you are subscribed to the right mailing list.

My math education is old and rusty, so any real mathematican should feel free to correct this message.