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.9 required=5.0 tests=BAYES_00 autolearn=ham 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: srt@zaphod.csci.unt.edu (Steve Tate) Subject: Re: What good is halting prob? Date: 1995/04/21 Message-ID: <3n8j0c$18u@hermes.unt.edu> X-Deja-AN: 101370075 distribution: world references: <3kaksj$iur@isnews.calpoly.edu> <3mve9b$gaj@news.cais.com> <3n27g6$4qr@kaiwan009.kaiwan.com> <3n3b82$ild@hermes.unt.edu> <3n7j9a$dks@kaiwan009.kaiwan.com> followup-to: comp.lang.ada,comp.edu organization: University of North Texas newsgroups: comp.lang.ada,comp.edu Date: 1995-04-21T00:00:00+00:00 List-Id: 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 |