Re: What good is halting prob?

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

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!

Sarcasm off.

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.

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.

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

I've heard complaints about Turing machines before, but almost
entirely from people who don't appreciate the theoretical work
that uses them.

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