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=0.1 required=5.0 tests=BAYES_05,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public From: srt@zaphod.csci.unt.edu (Steve Tate) Subject: Re: What good is halting prob? Date: 1995/04/19 Message-ID: <3n3b82$ild@hermes.unt.edu>#1/1 X-Deja-AN: 101283270 distribution: world references: <3kaksj$iur@isnews.calpoly.edu> <3mve9b$gaj@news.cais.com> <3n27g6$4qr@kaiwan009.kaiwan.com> followup-to: comp.lang.ada,comp.edu organization: University of North Texas newsgroups: comp.lang.ada,comp.edu Date: 1995-04-19T00:00:00+00:00 List-Id: 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 |