Re: Can you find anything wrong with this solution to the Halting Problem?

From: Chris Menzel (cmenzel_at_remove-this.tamu.edu)
Date: 07/25/04 

Date: 25 Jul 2004 19:50:30 GMT

On Sun, 25 Jul 2004 14:01:24 GMT, Peter Olcott <olcott@worldnet.att.net> said:
>> | > Then perhaps you could take Turing's original statement and proof and
>> | > point out which line or lines are in error.
>> |
>> | His original looks nothing at all like these simplifications that
>> | are comprehensible by far more people.

Actually, it is Turing's framework which is far simpler. No complex
programming language to learn, very simple simple description of the
machines and their behavior. A bright high school student has no
trouble understanding TMs and how to program them.

>> You have a computer science degree, most others here have computer
>> science degrees or maths degrees. If you want to be taken seriously,
>> I suggest you do the hard work needed to pinpoint the error in his
>> proof, which line or lines. Believe me, if you are right, we will
>
> They don't teach these kinds of proofs even at the graduate level
> in computer science. One could probably take some math courses
> that would apply toward elective credit.

Peter, Turing's proof of the unsolvability of the Halting Problem is a
*very* simple piece of elementary computability theory that can be found
in virtually any undergraduate text in automata theory and formal
languages. This is subject matter that is an essential part of any
serious undergraduate computer science curriculum, and is typically
encountered in one's third or fourth year of study in the US. The
Halting Problem would be considered remedial material in any legitimate
graduate computer science program in the world. If, as you claim, you
have an undergraduate degree in CS, and you never encountered the proof,
then you were, to say the least, poorly served by your undergraduate
institution.

Chris Menzel

Relevant Pages

  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... *very* simple piece of elementary computability theory that can be found ... serious undergraduate computer science curriculum, ... Halting Problem would be considered remedial material in any legitimate ...
    (comp.theory)
  • Advice for undergraduate schools?
    ... I'm looking for advice on what to look for in undergraduate ... I'm studying computer science, and I'm getting ready to transfer ... programming language design and type theory. ... for state schools would be especially helpful, ...
    (comp.theory)
  • Re: Busking - playing music in the street
    ... university menu when I was an undergraduate. ... Computer Science was not considered a subject, generally, until the ... become "Electrical Engineering and Computer Science" until about 1974, ... of MIT or CSAIL. ...
    (alt.usage.english)
  • Building a simple software firewall
    ... I'm a undergraduate currently pursuing my degree in computer science. ... Can anyone help me out in term of advices or resources? ...
    (comp.security.firewalls)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... >> of any serious undergraduate computer science curriculum, ... The Halting Problem would be considered remedial material in any ... > As I recall it was probably in the automata theory course that was an ...
    (sci.logic)