Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site unmvax.UUCP Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!whuxl!whuxlm!akgua!mcnc!philabs!cmcl2!lanl!unmvax!cliff From: cliff@unmvax.UUCP Newsgroups: net.arch Subject: Re: RMS v/s UNIX (non-religious) -- fun with TM Message-ID: <740@unmvax.UUCP> Date: Sun, 17-Mar-85 23:03:55 EST Article-I.D.: unmvax.740 Posted: Sun Mar 17 23:03:55 1985 Date-Received: Fri, 22-Mar-85 02:55:39 EST Organization: Univ. of New Mexico, Albuquerque Lines: 85 Here is the original claim that prompted my retort: **************************************************************************** Someone made the claim that there are some issues pertaining to locks that UNIX could not do at all even with libraries. This is clearly not true since VAX-UNIX can simulate a general Turing machine and can therefore perform ANY computable function. **************************************************************************** Many articles/letters have been written concerning my reply: **************************************************************************** Clear as mud...VAX-UNIX can't even simulate all finite automata, much less a turing machine. Does anyone out there have a machine that *can* simulate a turing machine? I want to put one next to my perpetual motion machine :-). **************************************************************************** TM are useful abstractions for many proofs, but the VAX-UNIX simulation paragraph is a crock. Not only can't VAX-UNIX simulate TM, it is irrelevant to "issues pertaining to locks." Here are a few answers/comments: 1. >do you have an example of a finite automata that >VAX/UNIX can't simulate There is only a fixed number of states that any VAX-UNIX configuration can be in (although this number is quite large), call this number N. It is impossible to simulate a FA that reads a "tape" and only accepts if the "tape" contains exactly N+1 1's on it. 2. >As with most things, it depends on your precise definitions. I >consider my VAX/UNIX machine to be a Turing machine since it has a tape >drive and the possibility of adding more modern mass storage devices as >they are developed. The tape is not infinite, nor is the control arbitrarily large. The article was about real VAX-UNIX machines (which is why the theoretical TM doesn't apply) ... you can claim that you can continually put new tape on it, but that does not make it so, the fact is you can't and that should be obvious. 3. >cliff, intending to impress us all with his wit and his intelligence, >notes that vax/unix is not a turing machine, for it "can't even >simulate all finite automata." tell us, cliff, what would you call a >machine that can simulate all finite automata? > peter Peter, you are almost correct. I was hoping my wit and intelligence would impress *you!* Why should I worry about the other schmucks...after all, you are the man, eh? Of course the answer to your question is either a Turing machine, or Wendy, depending on the zone (look at zee map). The point I was making is that since VAX-UNIX can't simulate all FA, it obviously can't simulate all TM (the redundancy is beside the point...look at how many people got stuck elsewhere). I am glad that I was less than explicit, otherwise I might not have had the chance to clarify my intent to impress you. I was so excited to see that not only did you read my article and find it worth replying to, but you actually knew my name! 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. 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? --Cliff [Matthews] {purdue, cmcl2, ihnp4}!lanl!unmvax!cliff {csu-cs, pur-ee, convex, gatech, ucbvax}!unmvax!cliff 4744 Trumbull S.E. - Albuquerque NM 87108 - (505) 265-9143