TM
A text-based, object-oriented,
Turing machine simulator
TM is based on the syntax of Elements of the Theory of
Computation by Lewis and Papadimitriou. The TM simulator
consists of three items:
- A simulator for executing Turing machine
- A preprocessor for Turing machine templates
- A development environment for building large Turing
machines out of simple ones
Here are the following files which you might find relevant:
- Documentation (approx 14 pages) describing how to use
this simulator. Available in pdf format.
- A tar-zipped file containing the source code, headers, and
makefile.
- Download and save tm.tar.Z
- Execute: uncompress tm.tar.Z
- Execute: tar -xf tm.tar
- Execute: make
This simulator is intended to be run on a linux/unix platform.
However, you should be able to get it to compile under a DOS/WIN
environment if you are willing to do a little work with makefiles
and projects.
Mini-tutorial:
For those of you who want to jump right in and get started, here
is a mini-tutorial. For more details, see the documentation above.
- Get, unzip, untar, and make the tm.tar.Z file above.
- Get, unzip, and untar the stuff.tar.Z file above.
- Look at an example Turing machine specification file:
L_.ab. This file has a Turing machine
which seeks and halts on the first blank to the left of the
read/write head. Look at this file for the syntax.
- Look at an example tape input file: tape1.
Look at the syntax. The * indicates the read/write head position
(the head is currently on the tape symbol just to the left of the
*.
- Execute: cat L_.ab tape1 | tm . See the results,
see the execution of the machine.
- Look at the file L_.i . This is a template which
is independant of a specific alphabet. Look at the file
alphabet.ab. This is a specific alphabet. Execute:
cat alphabet.ab L_.i | instantiate . The output should
be exactly the file L_.ab. This is how we store
templates and then instantiate them with a specific alphabet when
we need them. That way we don't have to create/store the same
Turing machine for each different alphabet.
- Look at the file simple.cc. This is an example
of how we combine numerous simple Turing machines into one
big Turing machine. Execute: simple < tape1 > outfile
and look at the contents of outfile.