Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site lanl.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!allegra!bellcore!decvax!genrad!panda!talcott!harvard!seismo!cmcl2!lanl!jlg
From: jlg@lanl.ARPA
Newsgroups: net.arch
Subject: Re: RMS v/s UNIX (non-religious) -- fun with TM
Message-ID: <23451@lanl.ARPA>
Date: Mon, 18-Mar-85 19:22:38 EST
Article-I.D.: lanl.23451
Posted: Mon Mar 18 19:22:38 1985
Date-Received: Fri, 22-Mar-85 00:55:05 EST
References: <740@unmvax.UUCP>
Sender: newsreader@lanl.ARPA
Organization: Los Alamos National Laboratory
Lines: 38

> 4. >MOST computers can SIMULATE a Turing machine.  The only thing that prevents
>    >them from being computationally equivalent to a Turing machine is the lack
>    >of an infinite store.  But even an infinite store can be SIMULATED by simply
>    >changing the disk packs as they fill.
> 
> I think you are confusing *very large* with infinite.

I think YOU are confusing 'simulation' with 'computational equivalence'.
The two are not synonymous.  'Infinite' can be simulated by 'very large',
it's fairly easy and I gave an example of how to do it.

> 5. >Theorems of computational equivalence
>    >can (and frequently are) applied to finite systems as well as infinite ones.
> 
> That is true, but your application was way off base.  First there is your claim
>   "since VAX-UNIX can simulate a general Turing machine and can therefore
>    perform ANY computable function."
> which is not even remotely true.  Then there is the fact that TM are models of
> computation, which does not always directly concern "issues pertaining to
> locks."  An example is the locking protocol of an Ethernet where there are
> real-time concerns ... "time" from a TM perspective is quite different from
> real-time.  Just how do you model an ethernet with a TM?

Real easy to model an ethernet with a Turing Machine - keep time as a
variable within the code.  This is how modeling is done.  A lot of physical
phenomena occur in time-frames of 10^(-10) seconds or less, no computer
(yet) can run this fast, but the phenomena CAN be modeled (we do it all the
time).

As for locks in VAX/UNIX vs.  VAX/VMS - both systems fail to be
computationally equivalent to Turing Machines in the same way: lack of
infinite store.  Therefore, any proceedure which works on a VAX/VMS system
can also be made to work on a VAX/UNIX system with, at most, an addition of
storage.  The VMS locking protocol supposedly works on VAX/VMS systems, so
it can also be implemented on a VAX/UNIX system.  If nothing else you can
simulate a bare VAX under UNIX and run VMS on that virtual machine.

J. Giles