Re: What good is halting prob?

[jmartin@kaiwan009.kaiwan.com (Jay M Martin)]

In <3n3b82$ild@hermes.unt.edu> srt@zaphod.csci.unt.edu (Steve Tate) writes:

>Jay M Martin (jmartin@kaiwan009.kaiwan.com) wrote:

>> I think Turing machines are pretty silly and see an idealized register
>> or random access machine as a much better way to present this stuff.

>Gee, it's nice of you to back this up with such solid reasoning!
>"Turing machines are pretty silly" --- what a great argument!

I think "silly" is a good discription for Turing machines, Goofy is another.
Come on, they are silly Rube Goldberg machines stamping symbols on 
infinite tapes that can move back and forth one position at a time.
Not my idea of a modern high-performance computer architecture!

>I have seen concepts from the theory of computing (both computability
>and complexity) presented in many different ways, including a
>presentation using register machines made by a famous
>mathematician/logician/recursion theorist.  Let me tell you this ---
>dealing with machine and state descriptions is much more elegant using
>a Turing machine than in *any* other model that I've seen.  The proof
>of Cook's theorem (NP-completeness) is fairly clean for a Turing
>machine, but becomes messy if you try to use a RAM.

For the halting problem, I found the register machine approach
clearer.  As for Cook's theorem look at Cormen for practical and
elegant proof.  No turing machines, no wierd definitions of
NP-complete as what is computable by a "non-deterministic Turing
machine" in polynomial time.  The proof is simpler than any Turing
machine proof I have ever seen.  Plus register machines, circuits etc,
build on useful computer concepts, not on some minimalist and useless
(in a practical sense) machine.

>The other point to make is that you should think about the
>Church-Turing thesis.  If approached from the point of view of a RAM,
>it's easy to have many doubts, such as how does the instruction set
>affect the computing power of the machine?  On the other hand,
>when looked at from the point of view of Turing machines, it seems
>like almost an obvious statement.
>Finally, for computational complexity issues such as how big registers
>are and what the instruction set is *do* strongly affect the results.
>There are no such "unseen assumptions" with Turing machines.

But this is assuming that this (possibly extra) thinking about these
issues with register/random access machines is not useful.  But it is
useful because these models are close to real machines and thus are
important to computer understanding in general.  As I see it, understanding
apparent paradoxes (doubts) with these machine models is worth the
(possibly) extra effort.

>> To me its just one of many "Dumb ideas of Computer Science" that are
>> sort of anarchisms but still survive.  

>Do you *really* think it has stuck around this long as the primary
>model of computation for theory of computing work from momentum
>rather than usefulness?  If other models are better, why are new
>proofs written using Turing machines?  Let me tell you why:  because
>the proofs are clean and elegant.

Yes, I do.  Computer Science (and other human endeavors) is filled
with silly, failed, culdesac-ed and incestuous fields and notations.
Are the proofs clean and elegant, or are you such a savant at Turing
Machines that they are "elegant" to you.  Maybe the proofs would be
more accessable to others if you guys stopped using Turing Machines.

So basically, as I see it, both the halting problem and
NP-Completeness can be presented without turing machines.  Since these
approaches more directly model real computers thus building on and
teaching practical computer concepts (circuits,random access
machines), I would expect students to connect more fully with this
approach (because it closer to reality).  So basically, I see no
pressing need to teach Turing Machines to 2 and 3rd year undergraduate
CS majors, it can taught to those specializing in the complexity
field.


Now get back to proving P != NP, I am tired of waiting.  :-)

Jay