Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!samsung!crackers!m2c!risky.ecs.umass.edu!dime!yodaiken From: yodaiken@chelm.cs.umass.edu (victor yodaiken) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <30082@dime.cs.umass.edu> Date: 4 May 91 14:55:55 GMT References: <333124@socrates.umd.edu> <30040@dime.cs.umass.edu> Sender: news@dime.cs.umass.edu Reply-To: yodaiken@chelm.cs.umass.edu (victor yodaiken) Organization: University of Massachusetts, Amherst Lines: 40 In article truesdel@nas.nasa.gov (David A. Truesdell) writes: >yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > >>>Last I heard, the Halting Problem was still insoluble. >>> >>>Is there some new theoretical result you'd like to share with us? > >>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. >-- >T.T.F.N., >dave truesdell (truesdel@nas.nasa.gov) 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. To suggest that type checking a compilable language is impossible because of the Turing theorem is to misapply the Turing theorem. In fact, even if we were to ignore the fundamental boundedness of actual computing devices, we would be wise to apply Turings theorem very cautiously. It is well known that there is no decision method for arithmetic, but number theorists don't seem to be too crippled by this situation. 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. 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.