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:
  1. A simulator for executing Turing machine
  2. A preprocessor for Turing machine templates
  3. A development environment for building large Turing machines out of simple ones
Here are the following files which you might find relevant: 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.
  1. Get, unzip, untar, and make the tm.tar.Z file above.
  2. Get, unzip, and untar the stuff.tar.Z file above.
  3. 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.
  4. 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 *.
  5. Execute: cat L_.ab tape1 | tm . See the results, see the execution of the machine.
  6. 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.
  7. 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.