Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!pacific.mps.ohio-state.edu!linac!midway!msuinfo!rang From: rang@cs.wisc.edu (Anton Rang) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: Date: 11 May 91 23:32:38 GMT References: <30040@dime.cs.umass.edu> <30275@dime.cs.umass.edu> Sender: news@msuinfo.cl.msu.edu Organization: UW-Madison CS department Lines: 21 In-Reply-To: truesdel@nas.nasa.gov's message of 9 May 91 03:03:32 GMT In article truesdel@nas.nasa.gov (David A. Truesdell) writes: >yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > >>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. > >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. It's not possible *if* your language allows you to represent all decidable functions and all computable relations. It may be that there are useful languages which do not have this property, though I'm not convinced of this. (Well, OK, finite-loop languages are useful for quite a few applications, I guess.) Anton +---------------------------+------------------+-------------+----------------+ | Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison | "VMS Forever!" | +---------------------------+------------------+-------------+----------------+