Path: utzoo!mnetor!uunet!husc6!bloom-beacon!mit-eddie!bbn!rochester!crowl
From: crowl@cs.rochester.edu (Lawrence Crowl)
Newsgroups: comp.lang.misc
Subject: Programming a Turing Machine
Message-ID: <9333@sol.ARPA>
Date: 4 May 88 14:13:09 GMT
References: <769@imagine.PAWL.RPI.EDU> <76700017@uiucdcsp> <843@actnyc.UUCP> <762@l.cc.purdue.edu> <1556@vaxb.calgary.UUCP> <438@ruuinf.UUCP> <4624@ihlpf.ATT.COM>
Reply-To: crowl@cs.rochester.edu (Lawrence Crowl)
Organization: U of Rochester, CS Dept, Rochester, NY
Lines: 16

In article <4624@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes:
>Seriously, the problem with a Turing machine is that it is simple with respect
>to the person implementing it.  Programming it is a nightmare!  (For those of
>you who don't think so, show me your Turing machine that implements the Unix
>kernal.  Until then, ... :-)) 

Programming a Turing machine is easy.  First, you program an emulator for a
simple RAM machine.  This is not difficult, you store address and value pairs
on the tape.  This costs at most quadratic slow-down.  (See Aho, Hopcroft, and
Ullman; "The Design and Analysis fo Computer Algorithms"; Addison Wesley 1974.)
Once you have a simple RAM machine, you can write an emulator for any existing
machine (like the 68000) and then the Unix port is relatively straight-forward.
-- 
  Lawrence Crowl		716-275-9499	University of Rochester
		      crowl@cs.rochester.edu	Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl	Rochester, New York,  14627