This is an implementation of a Turing machine simulator for UNIX.
Send any comments, bugs or improvements to Sergey.Berezin@cs.cmu.edu.

HOW TO INSTALL

Note: this program is supposed to run under UNIX.  If you cannot
compile it under Windoze, don't complain.  You'll only fall harder.

Under UNIX:
Get the distribution.  Normally it comes in a tar file, say
turing-0.99.tar.gz .  Unpack it:

% gunzip -c turing-0.99.tar.gz | tar xf -

or, if you have GNU tar, even simpler:

% tar zxf turing-0.99.tar.gz

It will create a directory "turing" and place all the files in there.
Then do the following:

% cd turing
% make

This should do the job.  You should see an executable file called
"turing".  If you get an error message, look into `makefile'.
Perhaps, you need to hack it up a bit for your particular system.


HOW TO RUN IT

In the directory where you installed it, type

% turing

This gives you the version number and usage info.  You can supply one
file with the description of your Turing machines and strings to run
them on, e.g.:

% turing example.tm

If the file name is a single dash `-', then the input is read from
stdin.  For example,

% cat example.tm | turing -

You will see an execution trace of every run you specify.  Note, that
the maximum number of steps in each run is restricted to 1000 by
default.  You can change the default to anything you like by setting a
macro MAX_STEPS in turing.c and recompiling.  You can also provide a
third parameter to the "run" command that will specify the max. number
of steps for that string.  However, 1000 should be sufficient for the
most of your needs in this class.

To supress the execution trace output and speed up the execution, use
options -q or -qq (`quiet' and `even quieter').  The first (-q) will
print only the first and the last configuration for each run, the
other one (-qq) supresses even that.  These options dramatically speed
up the execution (2-3K vs. 500M steps/sec on my slow machine).

The last option is -version, with the expected behavior.

All options can be placed anywhere in the command line string, and
only one input file can be provided at a time.

This program is an *interpreter*, which means that it will actually
execute every clause before moving to the next one.


INPUT LANGUAGE

The input language consists of a sequence of machine declarations and
their runs.  You can declare and run multiple machines in arbitrary
order, except that you need to declare the machine before you run it.

* Machine Declaration

Here you define a complete Turing machine: the states, the initial
state, the set of transitions, and, possibly, the set of final states.
The tape alphabet is all ASCII characters.

You can also define a DLBA (deterministic linearly bounded automaton)
using the keyword `DLBA' in place of `TuringMachine'.  DLBAs have
additional restrictions to the machine.  First, the tape is always
bounded by symbols @ and $ at the beginning and end respectively.
These symbols can not be used within the string.  Transitions are not
allowed to modify these symbols or to move accross them outside of the
tape.  When you run the machine, your input string will automatically
be surrounded by @ and $.  The tape length parameter is ignored in
`run' statements for DLBAs.

The declaration starts with a keyword `TuringMachine' followed by a
name (identifier), and the body of the declaration in curly braces.
The body has three parts starting with keywords `states', `initial',
and `transitions' declaring the obvious parts of the machine.  There
is also an optional `accepting' part.

`states' is followed by a comma-separated list of identifiers that
denote the states of the machine.  The list ends with a semicolon.

`initial' is followed by a state from the list of states, and a
semicolon.

`transitions' is followed by a sequence of transitions separated by
semicolons.  Each transition has a state-symbol pair on the LHS, an
arrow `->' separating the sides, and a new state, new symbol, and a
direction to move (`L',`N', or `R') on the RHS.  Each symbol has to be
enclosed into single quotes, like in C.  Note, that L,N and R are
keywords, so you can't use then as identifiers.

`accepting' is followed by a comma-separated list of states.  You can
also use the keyword `final' in this part, it has exactly the same
meaning.

To make a better sense of all this, look at this example:

TuringMachine test {
  states q0,q1,q3,q4;
  initial q0;
  transitions
    q0,'0' -> q1,'1',R;
    q0,'1' -> q1,'1',R;
    q1,'0' -> q0,'0',R;
    q1,'1' -> q0,'0',R;
    q1,' ' -> q3,' ',L;
    q0,' ' -> q3,' ',L;
    q3,'0' -> q3,'0',L;
    q3,'1' -> q3,'1',L;
    q3,' ' -> q4,' ',N;
    q4,' ' -> q4,' ',L;
}

A machine called `test' is defined with 4 states, initial state `q0',
and 10 transitions.

Note, that the Turing machine has to be deterministic.  That is, you
cannot have two transitions with the same LHS.


* Running the machine.

Now, after we've defined the machine `test', we can run it on a string
"0011" in any of the following ways:

test("0011");
test("0011",10);
test("0011",10,100);
test("0011",10,unlimited);

Here number 10 (the first argument) is the limit on the length of the
tape in both directions from the current position of the head.  The
default is 75.  The second argument is the maximum number of steps
allowed with the default 1000 (maximum 2^31, or ~2.0e9).  You can also
specify `unlimited' for the maximum number of steps.  In this case the
internal step counter can potentially count upto 10^18 steps, so you
can try Busy Beaver machines that take more than 2^31 steps to halt.


* Reading the output.

The output of the machine is a sequence of lines, one line per "clock
cycle".  Each line consists of the current tape contents and the state
of the machine put in angle brackets within the string.  The machine
is reading the symbol at right of the bracketed state.  For example,

11001<q2>aabb

means that the machine is reading the first symbol 'a' on the tape
"11001aabb", and is in the state q2.  I'm sure you'll figure it out as
soon as you see its running.

If there is no symbol to the right, then it is assumed to be ' '
(white space).

When it terminates, it prints the cause of termination (Halt, Loop
forever in the same state, ran over the tape/step limit) along with
acceptance information if there are accept states.

Normally, the simulator dumps its output to stdout.  However, you can
save the entire output in a file using redirect:

% turing test.tm > output.txt

The error messages will still go to the terminal (stderr), and will
not be saved in the file.


BUGS

I think I fished out most of them, but if you find one, please send me:

* your input file,

* the platform you are running it on 
  (run "uname -a" in xterm and copy the output),

* and describe what went wrong.

Also in the future the version number of the simulator would be handy.
To get it, run `turing' without any arguments.  And a fix too, if you
got it...

Sergey Berezin, November 2, 1998.
sergey.berezin at cs.cmu.edu