Lab 6: Turing Machine

This week, we have another lab that deals with linked lists. This time, however,
the list is a *doubly-linked list*, where each node contains two pointers,
one to the previous node and one to the next node in the list. The list will
be used to represent the tape for a *Turing Machine*, a kind of very simple,
abstract computing device that was introduced in the 1930's by Alan Turing as
a way of studying computation and its limitations. This lab must be finished
by next Wednesday.

**You should make sure that your work for last week's lab in in your CVS repository
and is up to date before noon on Wednesday, October 5.**

**You can begin the lab by creating a new Eclipse project and copying all the
files from the directory /classes/f07/cs225/files_for_lab_6
into that project.** Note that the files will contain many errors when you add them
to the project, because they depend on classes named

A Turing machine works on a "tape" that is used for both input and output.
The tape is made up of little squares called *cells* lined up in a horizontal
row that stretches, conceptually, off to infinity in both directions.
Each cell can hold one character. Initially, the content of a cell is a
blank space. One cell on the tape is considered to be the *current cell*.
As a Turing machine computes, it moves back and forth along the tape.
The current cell will represent the current location of the Turing machine.

A Turing machine tape can be represented by a doubly-linked list where each
cell has a pointer to the previous cell (to its left) and to the next cell (to its
right). Each cell can be represented as an object of type *Cell* as defined
by the class:

public class Cell { public char content; // The character in this cell. public Cell next; // Pointer to the cell to the right of this one. public Cell prev; // Pointer to the cell to the left of this one. }

This class is defined in the file Cell.java, so you don't have to write it yourself.

**Write a class named Tape to represent Turing machine tapes.**
The class should have an instance variable of type

-- returns the pointer that points to the current cell.**public Cell getCurrentCell()**-- returns the**public char getContent()***char*from the current cell.-- changes the**public void setContent(char ch)***char*in the current cell to the specified value.-- moves the current cell one position to the left along the tape. Note that if the current cell is the leftmost cell that exists, then a**public void moveLeft()****new**cell must be created and added to the tape at the left of the current cell, and then the current cell pointer can be moved to point to the new cell. The content of the new cell should be a blank space.-- moves the current cell one position to the right along the tape. Note that if the current cell is the rightmost cell that exists, then a**public void moveRight()****new**cell must be created and added to the tape at the right of the current cell, and then the current cell pointer can be moved to point to the new cell. The content of the new cell should be a blank space.-- returns a String consisting of the**public String getTapeContents()***chars*from all the cells on the tape, read from left to right. The current cell pointer should**not**be moved by this method. (This method is the hardest one to implement.)

It is also convenient to have a **constructor** that creates a tape that initially consists of a single
cell. The cell should contain a blank space, and the current cell pointer should point to it.
(The alternative -- letting the current cell pointer be null to represent an empty tape -- makes
all the methods in the class more difficult to implement.)

To **test** your *Tape* class, you can run the programs that are defined by
the files TestTape.java and
TestTapeGUI.java.

A Turing machine is a very simple computing device. (No one builds actual, physical Turing
machines; they are just abstract, conceptual devices.) A Turing machine has a *state*,
which can be thought of as a number that is stored in its internal memory. And it
has a *program* that consists of *rules* that tell it what to do at each stage
in its computation. When it computes, a Turing machine moves along a tape. It can see
the content of the current cell on the tape, and it can write a new character to that
cell. As it computes, its state can change. The computation is determined by the
machine's set of rules. Each rule contains five pieces of information: *currentState*,
*currentContent*, *newState*, *newContent*, and a boolean value, *moveLeft*.
A rule is applied when the state of the machine is *currentState* and the content in the
current cell is *currentContent*. When the rule is applied, three things happen:
The state of the machine is changed to *newState*, the character *newContent* is
written into the current cell, and the machine moves either one cell to the left or one
cell to the right. The direction of motion is determined by whether the value of *moveLeft*
is true or false. The Turing machine just repeats this process of finding the applicable rule
and applying it over and over -- except that when it enters a special state called the *halt
state*, the machine stops.

We will assume that the machine always starts its computation in state zero, and that the halt state is represented by any negative state number. During the execution of the machine, it is possible that the machine gets to some point where no rule is applicable. In that case, the machine will halt with an error.

To use a Turing machine to do a computation, the input for the computation is first written onto the tape and the current cell is set to some specified point in the input (by convention, the rightmost non-blank character in the input). The machine is started in state 0 and is allowed to compute until its state takes on a negative value, at which point it halts. The output of the computation is whatever is written on the tape at that point. Of course, it is possible that the computation will continue forever (like an infinite loop), or that it will halt with an error; in these cases, there is no output.

Write a *TuringMachine* class to represent Turing machines. The class must store the
list of rules that define the Turing machine. A rule is represented by an object of type
*Rule*. This class is already defined in the file Rule.java,
so you don't have to write it yourself. I strongly suggest that you store the list of rules
in an *ArrayList* (or in a *Vector* if you prefer). ArrayList is a standard class
in the package `java.util`, and you should already be familiar with it. If not, you can
read about it in Section 7.3 of the
textbook or in the Java API documentation. Your *TuringMachine* class must define
the following methods:

-- add a single rule to the list of rules for the machine.**public void addRule(Rule rule)**-- add all the rules from an array of**public void addRules(Rule[] rules)***Rule*to the list of rules for the machine.-- run the Turing machine on the given**public String run(Tape tape) throws IllegalStateException***Tape*, and return the contents of the tape when the machine halts; throw an*IllegalStateException*if at any point in the computation, no applicable rule can be found. The machine should start in state 0, and it should continue as long as the state is greater than or equal to zero. It should run in a loop that finds and executes an applicable rule each time through the loop. Note that the input to the machine is already written on the tape before this method is called.

You can test your *TuringMachine* class by running the main program defined by the
file TestTuringMachine.java.