Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!wuarchive!ukma!usenet.ins.cwru.edu!eagle!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: 9 May 91 03:03:32 GMT References: <30040@dime.cs.umass.edu> <30275@dime.cs.umass.edu> Sender: news@nas.nasa.gov Organization: NAS Program, NASA Ames Research Center, Moffett Field, CA Lines: 37 yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: >In article mathew@mantis.co.uk (CNEWS MUST DIE!) 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). >> >>I see. So you are claiming that it is possible to write a program to predict >>whether a given piece of code will terminate or not, for any compiled or >>interpreted programming language? >> >Sure. Can it be done in practice, for every language and every program? >I'll bet, no. But, there is no theoretical reason why a clever design >could not produce a useful programming language with a compiler that >verified termination. Oh terrific! You've spent the past several days pretending that you're an expert in the theory of computation. You've generated an impressive heap of buzzwords to defend your assertion that the halting problem does not apply to real computers, and then you produce the statement above. The answer to the question is "NO". It is not possible in practice, it is not possible in theory. THAT is what the halting problem tells us. It is impossible to do that type of analysis in a truly general fashion. Please read even a basic description of the problem before wasting any more net bandwidth. While it might be possible for a compiler to do this type of analysis on some SIMPLE programs, it's unlikely to work for even a moderately sized program, and one thing it wouldn't be able to compile and verify is itself. -- 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.'