Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!pacbell.com!att!linac!uwm.edu!spool.mu.edu!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: <30506@dime.cs.umass.edu>
Date: 14 May 91 14:20:35 GMT
References: <30275@dime.cs.umass.edu> <truesdel.673758212@sun418> <1991May14.054813.18427@sbcs.sunysb.edu>
Sender: news@dime.cs.umass.edu
Organization: University of Massachusetts, Amherst
Lines: 30

In article <1991May14.054813.18427@sbcs.sunysb.edu> jallen@csserv2.ic.sunysb.edu (Joseph Allen) writes:
>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?
>
>-- 

Care to explain why these features make a language turing uncomputable?
And please explain why primitive recursive functions are then, contrary
to common belief, turing uncomputable.


>/*  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]]);}