Article View: comp.lang.misc
Article #5510Programming a Turing Machine
From: Lawrence Crowl
Date: Wed, 04 May 1988 14:13
Date: Wed, 04 May 1988 14:13
16 lines
1556 bytes
1556 bytes
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
Technical Details
Message-ID:
<9333@sol.ARPA>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!uunet!husc6!bloom-beacon!mit-eddie!bbn!rochester!crowlReferences:
<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>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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