In this lab, you will be doing several exercises with linked lists. To add some context to the exercises, the lists that you will work on are part of the implementation of Turing machines. Turing machines are described below, and there is an applet version of the Turing machine program later on this page that you should try out.
You should start a new Eclipse project named lab4. Copy the entire folder named turing from /classes/s10/cs225 into your project. (You can also get the folder by downloading turing.zip and unzipping it.) Be sure to add the entire folder to the src directory in the Eclipse project. There will be errors in the project because of missing classes that you will have to write. The turing folder is a package, and it contains two subpackages named turing.machine and turing.test. All the classes that you will use in this lab are defined in one of these packages rather than in the default package. If you are unfamiliar with packages, you should review Section 2.6.4 and Section 4.5.3, and ask for help if you need it.
This lab is due next Thursday, at the beginning of lab.
A Turing machine is an abstract computing machine, not a physical device. Turing machines are named after the British mathematician Alan Turing, who invented them to use as a simple model of mechanical computation. Although Turing machines are very simple, they can be used to solve the same set of problems as any computer.
A Turing machine has several parts:
When the Turing machine runs, it will start in state 0 and then execute rules until it enters the halt state; if that never happens, then it will run forever. To perform a computation with a Turing machine, you should write the input for the machine on the tape, with the machine placed, by convention, on the right end of the input string. The machine starts in state 0. Start the machine and let it run until it halts. The output of the computation is whatever is written on the tape at that time.
Here is a simple GUI version of the Turing machine program that you will be working on in this lab. There are several example machines that you can load using the "Load Example" menu. Click on "Step" to get the machine to execute one rule. Click on "Run" to get the machine to run until it halts.
The basic classes for implementing Turing machines can be found in the package turing.machine. The class TMRule represents one of the rules in a Turing machine program. A program consists of a collection of TMRules, and there should be a class to represent such a program. Currently, that class is missing. The first part of the lab is to write that class.
A TMRule tells a Turing machine what what action to take if it is in state stateIn and if it sees character charIn in the current cell. If rule is of type TMRule, then rule has methods rule.getStateIn(), rule.getCharIn(), and rule.getAction() to get the three parts of the rule. The action is an object of type TMAction.
You should write the class that represents a program as a collection of TMRules. To work with the rest of the program, the class must be named RuleSet and must be in the package turing.machine. It must implement the following methods:
public void addRule(TMRule rule)
-- adds the specified rule to the program
public TMAction getAction( char charIn, int stateIn )
-- if there is a rule in the program with the specified
charIn and stateIn, then return the TMAction part
of that rule. If no such rule exists, return null.
Since this is a lab on linked lists, you must implement the collection of rules as a linked list (and you must construct that list yourself, not use the standard LinkedList class). A linked list is actually not the best implementation. Later in the course, we might come up with a better one.
You should use a singly linked list where each node contains one TMRule. You will need a class to represent a list node; you can define it as a static nested class inside the RuleSet class. The addRule method can simply add a new node at the head of the list. The getAction method will have to search the list to find the appropriate rule, if one exists.
Once you have written your class, there should be no errors in the program TestRuleSet, which you will find in the package turing.test. You can run that program to test your RuleSet class.
Also missing in the Turing Machine project is a class named Tape to represent the tape of a Turing machine. You should create this class in the package turing.machine.
You should represent a tape as a doubly linked list. A tape consists of a sequence of cells. In the Tape class, each cell of the tape is represented by one node in the doubly linked list. The node contains a single character, which is the contents of the cell. The node is linked to the preceding cell and to the following cell.
You won't necessarily need pointers to the beginning and to the end of the list. You will need a pointer that points to the "current cell." This is the cell where the Turing machine is located; it is the only cell that the Turing machine can "see" at a given time. Typically, the current cell is somewhere in the middle of the list.
When the Turing machine moves left or right, the current cell pointer has to be moved to the preceding node or to the next node in the list. This leads to one problem: Although the tape is conceptually infinite, the list is not actually infinite. If the current cell pointer is at the beginning of the list, and the machine wants to move left, you have to add a new node to the beginning of the list before moving. Similarly, for the other end of the list. A newly created node should contain the blank character, ' '.
To work with the rest of the program, the Tape class must contain the following:
public Tape()
-- The constructor should create a tape that is initially completely blank.
(It will be easiest if you make a list with one node, containing a blank
character, to represent an empty tape.)
public char getCurrentChar()
-- A trivial method that returns the character in the current cell.
public void apply(char charOut, int move)
-- put charOut into the current cell, then move one cell over in the
direction indicated by the second parameter. The second parameter is
one of the constants TMAction.LEFT or TMAction.RIGHT, telling you to
move the current cell pointer left or right (that is, to the preceding
node or to the next node).
public void setContents(String str)
-- This method is used to provide input to the Turing machine. It should
replace the list with a new list that contains all the characters from
the string str, one to a node. The current cell pointer should point
to the final node, which contains the last character of str. In the
case where str is null or is the empty string, a new blank tape should
be created.
public String getContents(String str)
-- This method is used to read the output of a Turing machine computation
It should return a string that contains all the characters from the
tape, put together into a string. It is not necessary to return
leading or trailing blank characters; for example, you can collect
all the characters into a string str, then return str.trim().
The last three methods are easy to write. You will have to think carefully about what you want to do with the list. Draw some pictures! It is especially important when constructing the list that all the pointers are set up correctly.
Once you have the class written, you can test it by running the program TestTape in the package turing.test. When you've completed both parts of the lab, you will have a complete implementation of Turing machines. You can test it with the program TestTuringMachine in the package turing.test and with TuringMachineGUI in the package turing.