From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public From: jmartin@kaiwan009.kaiwan.com (Jay M Martin) Subject: Re: What good is halting prob? Date: 1995/04/20 Message-ID: <3n7j9a$dks@kaiwan009.kaiwan.com>#1/1 X-Deja-AN: 101283321 references: <3kaksj$iur@isnews.calpoly.edu> <3mve9b$gaj@news.cais.com> <3n27g6$4qr@kaiwan009.kaiwan.com> <3n3b82$ild@hermes.unt.edu> organization: KAIWAN Internet (310-527-4279,818-756-0180,909-785-9712,714-638-4133,805-294-9338) newsgroups: comp.lang.ada,comp.edu Date: 1995-04-20T00:00:00+00:00 List-Id: 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