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 Tape and TuringMachine that are not yet defined. You job for this lab is to write those classes.
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 Cell that points to the current cell. To be compatible with the classes that will use the Tape class, your class must include the following methods:
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:
You can test your TuringMachine class by running the main program defined by the file TestTuringMachine.java.