Newsgroups: bit.listserv.words-l
Date:         Tue, 14 Apr 1992 10:50:01 +0200
 <WORDS-L%UGA.bitnet@VTVM2.CC.VT.EDU>
From:         torkel%SICS.SE@VTVM2.CC.VT.EDU
Subject:      Re: CALLING ALL STUDENTS OF RUSSIAN
Comments: To: WORDS-L@uga.cc.uga.edu

  Frank writes:

  >Godel's work was in decidability...very much a sister field of
  >computability.
  >Both Turing and Godel did work in answering Hilbert's challenge. Godel
  >created the halting problem and Turing proved that it was unsolvable.

  Sorry, but this is completely garbled. Godel had nothing to do with the
halting problem. The very definition of the halting problem appeared only
with Turing's introduction of Turing machines (1936-37). You're confusing
two different concepts of decidability. Turing did indeed prove the
undecidability (by Turing machines) of the halting problem for Turing
machines. That is to say, he proved that a certain function is not
Turing computable. Godel's theorems concern decidability in formal
theories: they establish that under certain assumptions there exists, given a
theory T, a statement A such that A is undecidable in T, i.e. neither
A nor its negation is provable in T. The two concepts are not unconnected,
but Godel's work dealt strictly with the latter.


  >But all of his work was pen and paper theory.  He never wrote a computer
  >program (at least none of significance) and he never constructed or
  >directly supervised the construction of a computer.

  I'm pretty sure you're quite wrong about this. Unfortunately, I don't
have at hand the article in which I read about Turing's involvement in
the actual construction of computers, so I can't give any reference.
However, it's easy to check it out e.g. in the standard Turing biography, so
there's no point in arguing over it.

  >Interesting.  What did he demonstrate with his turing machine principles
  >then?  Enquiring minds want to know...

  I don't know just what you mean by "turing machine principles", but
I'll assume you refer to his definition of what we now call Turing
machines. What Turing did in his paper "On computable numbers, with an
application to the Entscheidungsproblem" was to define the concept of
a Turing machine and thereby the concept of Turing computability, to
argue (not demonstrate!) that all mechanically computable functions
are Turing computable, to prove the Turing unsolvability of the
halting problem for Turing machines, and to conclude further (the
"application") that the so-called Entscheidungsproblem is unsolvable
by Turing machines. (He also, as the title suggests, defined the
concept of computable real numbers.) In a later paper he proved the
equivalence of Turing computability and computability in the lambda
calculus.

  Apart from this and his important practical work (the cracking of the
German Enigma machine and the building of computers), Turing is best known
for i) his work on "ordinal logics", ii) his article "Can a machine think",
in which he proposed to replace the question of the title by the question
whether a machine can pass the Turing test.

  >There is indeed a Church-Turing thesis (so named because it was developed
  >independently by both at about the same time).  And this thesis is
  >directly related to the halting problem.

  Certainly there is a Church-Turing thesis, but no "Church-Turing thesis
on the halting problem".

   >Note that, as you say, it
   >is a THESIS, not a PROOF.  That I can see Graham never argued otherwise.

  Look a bit closer. Graham spoke of Turing's "proof that all
computation models can be reduced to a Turing machine."

  >Wow.  I can say that too...see:
  >Hmm...

  Ah, but my humming can lick your humming.
Comments: Gated by NETNEWS@AUVM.AMERICAN.EDU