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.225337.24416@sbcs.sunysb.edu>
Date: 18 May 91 22:53:37 GMT
References: <30082@dime.cs.umass.edu> <1991May5.135342.13792@daffy.cs.wisc.edu> <30164@dime.cs.umass.edu>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Organization: State University of New York at Stony Brook
Lines: 26

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.

>Pointing it out is nice, but most computer engineers would be surprised by
>this claim. If we build a device from 3dimensional switching elements, there
>are only two alternatives --- finite state device, or infinite volume device. 
>Of course, if we ignore the discrete nature of the switching elements and
>start worrying about analog behavior then things are different.

I'm a communications ee (well almost anyway) and I'll make this statement even
stronger.  Even if the device is analog, you still have a finite amount of
information because of noise and QM.  Therefore it's still a FSM- only each
state is not exactly known (the state is a probability function instead).

And I'm almost 100% sure about this statement: the whole universe has a
finite amount of information in it if it has a finite amount of energy. 

But this is getting a little silly.  Whether finite programs are haltable is
also unprovable (right? CS people?).
-- 
/*  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]]);}