🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.misc
Article #3961

Re: Halting Problem Solved! Film at 11! (Was Re: definitions)

#3961
From: Joseph Allen
Date: Tue, 14 May 1991 05:48
23 lines
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!jallen
References: <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