Programming Project #4: Simulation of Turing Machines
Assigned: Fri 13 Apr 2001
Due: Fri 27 Apr 2001
For this project you will write a program similar to that which you wrote for the
lab on NFAs, except now it should simulate the computation performed by a
full-fledged Turing Machine. As before, the program should be
parameterized (or modular) with respect to the actual TM which is simulated;
i.e., it should be possible for the user to configure the program with a
specific TM and then run that TM on several inputs.
In particular, your program should be able to:
As usual, you may use any language or platform you wish for your
implementation; the only restriction is that you be able to demonstrate your
program for the instructor, either in lab during regularly scheduled hours, or
by advance appointment in some other easily accessible place (e.g., the student
research lab, WITS labs, instructor's office, etc.).
For your demo, it should be possible for you to quickly enter in
a Turing Machine of reasonable size (say, about 5 to 10 states) on the
basis of a state diagram or other description of the TM.
As per previous assignments, we will assume that all alphabets will include
only printable ASCII characters and that states will be named
according to the usual programming language conventions for identifiers (i.e., sequence
of letters and numbers starting with a letter).
In order to enter your TM's description, you may use either a text-based interface,
a graphical interface or a combination of the two. It is recommended that you
at least consider basing your format on the one used in the Sipser textbook,
since that is how I will most likely come up with examples for you to run
(recall that Sipser uses state-transition diagrams with edges labelled by
triples of the form "a->b,D" where "a" and "b" are members of the tape
alphabet and D is a "direction, either Left or Right).
Remember that a Turing Machine reads and writes tape symbols, which include
the usual input alphabet, plus the special blank symbol (you can use either
a standard blank or, for readability, perhaps an underscore) and possibly others.
You may want to implement some "shortcuts", so that you don't always have to
specify the full delta transition function, or so that you can specify
"don't move" transitions easily.
Unlike NFAs, Turing Machines are deterministic, at least as they are originally
defined in the Sipser text. We'll use this definition for the purposes of the
lab, which should make your job easier (no queues, no alternative futures, etc.).
In fact, because of determinism and the lack of epsilon transitions, Turing
Machines are in many ways more like DFAs than like NFAs, the only major
difference being the use of the tape (in other words, the finite control
is essentially the same). You may wish to go back to your DFA code from Lab #1
as a basis for your TM code.
Regarding output format, you have wide leeway to choose a form that you think will
be easy to read and work with. However, it should be possible to read off from
the trace which state the machine is in, what is on its tape and which position of
the tape its read/write head is over. As a bare minimum, you could use the
configuration notation given in the Sipser textbook, modified so that the name
of the current state is offset better from the tape contents. In any case, you
will probably want to allow for stepping through the trace and for a certain amount
of visible "history" (e.g., previous trace steps in a text window) in order to
facilitate debugging.
