Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!wuarchive!uunet!stanford.edu!agate!sag4.ssl.berkeley.edu!jwl From: jwl@sag4.ssl.berkeley.edu (Jim Lewis) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <1991May4.224936.11304@agate.berkeley.edu> Date: 4 May 91 22:49:36 GMT References: <30040@dime.cs.umass.edu> <30082@dime.cs.umass.edu> Sender: root@agate.berkeley.edu (Charlie Root) Organization: Space Science Labs Lines: 50 In article <30082@dime.cs.umass.edu> 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). -> ->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. 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. This thread began when someone mentioned the relationship between strong typing and the problem of deciding whether a given function specifies a terminating computation. In this context, "termination" is generally understood to be a property of the algorithm (and perhaps its input), NOT the machine used to run the algorithm. Your formulation requires us to tie the definition of "terminating" to a specific compiler and machine configuration (including the amount of off-line storage available for the computation). It's about as useful and interesting as saying that "Fermat's conjecture is true (in BASIC on a TRS-80 with 4k of memory...)" -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. It is also the case that there is no general algorithm to solve the halting problem for *any* universal TM. And decision procedures for the halting problem on non-universal TM's (e.g. the ones that are equivalent to FSMs) usually aren't very interesting, because they don't tell you what happens if you throw a bigger state space at the problem. ->>The sooner computer scientists begin to understand the actual meaning ->>of the undecidability and complexity results, the better off the filed ->>will be. On behalf of computer scientists everywhere, "Eat my shorts!" :-) -- Jim Lewis U.C. Berkeley