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.
My math education is old and rusty, so any real mathematican should feel free to correct this message.