Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!samsung!crackers!m2c!risky.ecs.umass.edu!dime!chelm.cs.umass.edu!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: <30514@dime.cs.umass.edu> Date: 14 May 91 15:55:13 GMT References: <1991May14.054813.18427@sbcs.sunysb.edu> Sender: news@dime.cs.umass.edu Organization: University of Massachusetts, Amherst Lines: 37 In article rockwell@socrates.umd.edu (Raul Rockwell) writes: > > >Victor Yodaiken: > >>But, there is no theoretical reason why a clever design could not > >>produce a useful programming language with a compiler that > >>verified termination. > > David A. Truesdell: > >The answer to the question is "NO". It is not possible in > >practice, it is not possible in theory. > >Joseph Allen: > No, it can be done! Really! Just don't allow loops, gotos or > recursion. Now who wants to write a compiler in a language with > these restrictions? > >Well, you can allow loops as long as they can guaranteed to be >bounded. And you don't really need a new compiler, just take an >existing one and remove anything which allows unbounded loops or >recursion. > The kind of looping that makes Turing machines undecidable is quite different from the kind of looping we get in real machines. On a turing machine while(true)i = i+1; is a truly infinite loop, each iteration takes us to a new state. But on a real computer, while(true)i = i+1; *will* repeat state (or crash the program). Here we have a *finite* loop. Similarly, bounded recursion, even with implicit bounds, is all we have on real computers -- eventually stacks will overflow. So it is, in principle, quite possible to write an ANSI "C" compiler that would detect non-terminating loops. The compiler would have to know someting about the limits of adressable memory onthe machine, but, that does not seem unreasonable.