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: <1991May19.024820.25262@sbcs.sunysb.edu>
Date: 19 May 91 02:48:20 GMT
References: <1991May5.135342.13792@daffy.cs.wisc.edu> <30164@dime.cs.umass.edu> <1991May18.225337.24416@sbcs.sunysb.edu>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Organization: State University of New York at Stony Brook
Lines: 37

In article <1991May18.225337.24416@sbcs.sunysb.edu> jallen@eeserv1.ic.sunysb.edu (Joseph Allen) writes:
>In article <30164@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>>In article <1991May5.135342.13792@daffy.cs.wisc.edu> quale@khan.cs.wisc.edu (Douglas E. Quale) writes:
>>>In article <30082@dime.cs.umass.edu> yodaiken@chelm.cs.umass.edu (victor yodaiken) writes:
>>>I should also point out that real computers are *not* finite state machines.

>But this is getting a little silly.  Whether programs on finite machines will
>halt is also unprovable.  Isn't it?

Ack!  I apologize for wasting net bandwidth.  The following article answers
this question:

From: yodaiken@chelm.cs.umass.edu (victor yodaiken)
>[A finite TM is translatable into a FSM.  A FSM has a state space S and a
>mapping S -> S.  To see if it halts, pick a starting state, run through the
>sequences.  If if goes on the halt state then it halts.  If it ever touches a
>state which already occured, it doesn't.  Since there is only a finite number
>of states, it takes a finite amount of time to decide (since at most it has
>to go through all the states)]

So on any real computer with no I/O, you would know.  Often it will halt
because of a "segmentation fault -- stack overflow -- core dumped" when on a
real TM it is undecidable. 

Now the entire universe can be modeled with a FSM with part of the state being
random for each step.  (This assumes the universe has finite storage capacity;
which I believe to be true if there's a finite amount of energy in the
universe) If you run a program on a computer in the universey ou get three
possible answers: halts, doesn't, undecidable. Obviously if the haltability
depends on the randomness then it's not decidable.  For some cases you can
tell if it depends, for others you can't.  The random part is kind of a door
to an infinite state space.  Hmm... 
-- 
/*  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]]);}