CPSC 225, Spring 2010
Lab 4: List Exercises (with Turing Machines)


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.


About Turing Machines

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:

  1. A "tape" made up of "cells," where each cell can contain one character. Conceptually, the tape is infinite in both directions, but cells that have never been assigned any data are considered to contain a blank character, and only the finite non-blank part of the tape really needs to be represented.
  2. The "CPU" of the machine, which can move back and forth on the tape, reading and writing characters. The CPU can only see one cell at a time, and it has no memory of previous cells that it has seen. The CPU has one number in its internal memory, which is called its "state." The state can be a non-negative integer, or it can have the special value -1, which is called the "halt state".
  3. A set of "rules," which constitute the program for the machine. In each step of its computation, the machine applies one rule. Which rule it applies depends on what its current state is and what character it sees in the current cell. The rule has a three-part action that tells the machine what character to write in the current cell (possibly the one that is already there), what state to change to (possibly stay in the same state), and which direction to move (left or right). The machine always moves one cell to the left or to the right when it executes a rule.

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 List of Rules

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.


The Tape as a Doubly Linked List

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.


David Eck, for CPSC 225