Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!sbcs!csserv2.ic.sunysb.edu!jallen From: jallen@csserv2.ic.sunysb.edu (Joseph Allen) Newsgroups: comp.lang.misc Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions) Message-ID: <1991May14.054813.18427@sbcs.sunysb.edu> Date: 14 May 91 05:48:13 GMT References: <30275@dime.cs.umass.edu> Sender: usenet@sbcs.sunysb.edu (Usenet poster) Organization: State University of New York at Stony Brook Lines: 23 In article truesdel@nas.nasa.gov (David A. Truesdell) writes: >yodaiken@chelm.cs.umass.edu (victor yodaiken) writes: > >>In article mathew@mantis.co.uk (CNEWS MUST DIE!) 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. 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? -- /* jallen@ic.sunysb.edu */ /* Amazing */ /* Joe Allen 129.49.12.74 */ int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0) +r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2 ]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}