Article View: comp.lang.misc
Article #3961Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
From: Joseph Allen
Date: Tue, 14 May 1991 05:48
Date: Tue, 14 May 1991 05:48
23 lines
1866 bytes
1866 bytes
In article <truesdel.673758212@sun418> truesdel@nas.nasa.gov (David A. Truesdell) writes:
>yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>
>>In article <a8uk215w164w@mantis.co.uk> 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]]);}
Technical Details
Message-ID:
<1991May14.054813.18427@sbcs.sunysb.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!sbcs!csserv2.ic.sunysb.edu!jallenReferences:
<a8uk215w164w@mantis.co.uk> <30275@dime.cs.umass.edu> <truesdel.673758212@sun418>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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: <a8uk215w164w@mantis.co.uk> <30275@dime.cs.umass.edu> <truesdel.673758212@sun418> Sender: usenet@sbcs.sunysb.edu (Usenet poster) Organization: State University of New York at Stony Brook Lines: 23