Re: What good is halting prob?

[srt@zaphod.csci.unt.edu (Steve Tate)]

Jay M Martin (jmartin@kaiwan009.kaiwan.com) wrote:
> In <3n3b82$ild@hermes.unt.edu> srt@zaphod.csci.unt.edu (Steve Tate) writes:

> >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.  

In a partial way, what you say is true, but if you look a little more
carefully at the presentation in CLR it actually supports what I said
above.  The concepts of NP-completeness are presented in a very clean
and clear way in CLR.  But not using Turing machines makes the proof
of Cook's theorem messy and difficult.  In fact, it gets so messy that
CLR doesn't even present the full proof!!!  To quote them: "The actual
proof of this fact is full of technical intricacies, and so we shall
settle for a sketch of the proof based on some understanding of the
workings of computer hardware."  Using a Turing Machine the proof is
very clear and isn't based on some vague "understanding of the
workings of computer hardware".

> Plus register machines, circuits etc,
> build on useful computer concepts, not on some minimalist and useless
> (in a practical sense) machine.

It depends on what you call "practical".  If you're interested in
writing programs, then Turing machines aren't very practical.  If
you're interested in proving theorems, they *are* very practical.

> >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.

Very true --- but doesn't it make sense to lay down the unambiguous
framework (using Turing Machines) first, and then use that as a basis
for discussing the apparent paradoxes with the more computer-hardware
oriented models?  If you don't establish the firm basis first, what
do you use as a point of reference?

> >> 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.

Are you claiming that proofs need to be accessible to someone
not trained in the field?  I don't understand why that's a
particularly good goal at all.  Imagine if someone had said to Wiles
"My, that's a nice proof of Fermat's Last Theorem, but why didn't you
write it in a way that's accessible to everyone?"  The point is, that
work builds on other work --- if there is an easier and more elegant
way to approach the work it will be taken, but to make proofs more
complicated in order to base them on more common ground is not a
direction I'm interested in taking.

> 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.

And I see no pressing need to "dumb down" the curriculum by not
talking about Turing machines.  It may take a different outlook than
the typical "program this" attitude of many other courses, but
struggling to get the concepts is very valuable and provides excellent
additional insight.  Education isn't supposed to always be easy or
entertaining, and we are trying to educate computer *scientists*,
not computer *programmers*.

--
Steve Tate  ---  srt@cs.unt.edu | "As often as a study is cultivated by narrow
Dept. of Computer Sciences      |  minds, they will draw from it narrow
University of North Texas       |  conclusions."  -- John Stuart Mill, 1865.
Denton, TX  76201               |