Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cmcl2!sbcs!eeserv1.ic.sunysb.edu!jallen
From: jallen@eeserv1.ic.sunysb.edu (Joseph Allen)
Newsgroups: comp.lang.misc
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <1991May18.214429.23987@sbcs.sunysb.edu>
Date: 18 May 91 21:44:29 GMT
References: <truesdel.673758212@sun418> <1991May14.054813.18427@sbcs.sunysb.edu> <30506@dime.cs.umass.edu>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Organization: State University of New York at Stony Brook
Lines: 43

In article <30506@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>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:
>>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?

You need loops to have an infinite loop.  If you don't have infinite loops,
the program will halt.  Naturaly "loop" is a bit broad (as an other poster
pointed out, many loops can easily be proved to/not to terminate)

>And please explain why primitive recursive functions are then, contrary
>to common belief, turing uncomputable.

I'll transform the problem:

/* 6502 Simulator */

char ram[65536],a,x,y,sp,cc; short pc;

run() {
 switch(ram[pc++]) {
  /* a case...break for each 6502 instruction */
 case HLT: return; }
 run(); }

main() { /* Load program into ram */ pc=ram[0xfffe]+ram[0xffff]*256; run(); }

So now all you have to do is prove the haltability of any program you can make
on a 6502 microprocessor.  (the simulator does assume an infinite stack space,
but if we're talking about turing machines...) 

I think "primitive recursive functions" must mean something different from
what I was talking about.

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