Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!mips!ptimtc!nntp-server.caltech.edu!mustang!data.nas.nasa.gov!sun418.nas.nasa.gov!truesdel From: truesdel@nas.nasa.gov (David A. Truesdell) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 5 May 91 20:18:21 GMT References: <333124@socrates.umd.edu> <30040@dime.cs.umass.edu> <30082@dime.cs.umass.edu> Sender: news@nas.nasa.gov Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA Lines: 54 yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article truesdel@nas.nasa.gov (David A. Truesdell) writes: >>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >> >>>The halting problem does not really apply to actual programming languages >>>(i.e. those that are compiled or interpreted into machine code). >>>The sooner computer scientists begin to understand the actual meaning >>>of the undecidability and complexity results, the better off the filed >>>will be. >> >>Care to share the reason why the halting problem does not apply? Or, is >>this just some handwaving by someone who really doesn't understand what the >>halting problem means. >Real computers correspond to finite state machines not turing machines, >thus the halting problem is trivially (in theory of course, not in >practice) solvable for real computers. Wrong! Last time I looked, a Turing machine consisted of a finite state machine and an infinitely large memory. "Real computers" really differ only in that they have a finite amount of memory. > If you provide a formal >language L and an algorithm C that will transform programs over >L into machine language for a reasonable computing device, then >C transforms L programs into finite state machines. In these >situations, the pumping lemma is of far more interest than the >halting problem. Of course you leave "reasonable" undefined. :-) Other than that, it seems that the since the halting problem doesn't "interest" you, it isn't important. You sound like a typical academic. > Turing showed that there was >*no general algorithm* that would solve the halting problem for all >turing machines. This does not mean that there is no algorithm for >solving the halting problem for all interesting cases. I'd guess your definition of "interesting" probably means "trivial". > Turing's >result should be of interest primarily to meta-mathematicians and >logicians. Those concerned with applied mathematics, and programming >languages certainly seems applied, don't really have to worry about it. Beware, problems of "theoretical interest only" have this nasty habit of sneaking up and biting you on the ass. -- T.T.F.N., dave truesdell (truesdel@nas.nasa.gov) 'And Ritchie said, "Let there be portability!" And nothing happened, so Ritchie realized that he had his work cut out for him.'