Warmup Exercise: Simple Linked List

As a warmup, you will implement a simple linked list. You will work in the file SimpleList.java. Except for the missing list implementation, this is already a complete program. The work that you will have to do on this exercise is almost identical to examples that you have seen in the book and on the board. Hopefully, typing in the code and getting it to work will help you to understand linked lists.

You will need to define a class to represent a node in the list. You can define a "private static class" inside the file SimpleList.java for that purpose. The items in the list are of type String. Use a global static variable to represent the head of the list.

You need to complete the methods named add and find. Read the comments on those methods. The add() method can add the word at the head of the list. The find method needs to return the position of the word in the list, if it finds the word. The positions are not stored in the list. Just count the nodes as you traverse the list.

Here is the input/output from a run of my completed version of the program:

Type some words, one to a line.  Press return to end.
? fred
? wilma
? barney
? betty
? pebbles
? 

Your words have been added to the list.
Enter words to be tested, one to a line.  Press return to end,
? bambam
   bambam was not found in the list.
? pebbles
   pebbles was found in the list at postion 1.
? fred
   fred was found in the list at postion 5.
? 

About Turing Machines

In the second exercise for the lab, you will write one part of a program that simulates Turing machines. To do the exercise, you need to know just a little about them. 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—or they could if they existed. (In fact, a Turing Machine can solve more problems than any real computer, since it has unlimited memory.)

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. The tape is the main memory of the machine.
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 a special value 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 number zero 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. Start the machine 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.

You can find a runnable version of the Turing machine program that you will be working on in the executable jar file /classes/cs225/SimpleTuringMachine.jar. When you run the program, you will find a "Load Example" menu. There are several example machines in the menu. After loading an example, click on "Step" to get the machine to do one step of its computation. Click on "Run" to get the machine to run, rather slowly, until it halts.

Doubly-linked List Exercise: Tape for a Turing Machine

The Turing Machine program is defined in the package named turing. The program is incomplete. The only part that is missing is the code that implements the tape of the Turing Machine, in the file Tape.java, in the package turning.machine. The class has a constructor and four methods, but none of them do anything. Your assignment is to complete this class. You do not have to make any changes to the program outside the the file Tape.java.

A tape should be represented as a doubly linked list. A Turing machine tape consists of a sequence of cells. In the Tape class, each cell of the tape will be represented by one node in the doubly linked list. The item in the node is a single char value, which represents the character in the cell. The node must be linked to the preceding cell and to the following cell in the list. You have to create the class that represents the individual nodes in the list. You can create it as a "private static class" inside Tape.java.

You won't need pointers to the beginning or to the end of the list (although keeping a pointer to the left end of the list would make it easier to implement one of the methods). What you will definitely need is a pointer that points to the "current cell," which will generally be somewhere in the middle of the list. The current cell is the cell where the Turing machine is located; it is the only cell that the Turing machine can "see" at a given time. The list that represents a tape containing the word "Hello", with the current cell being the one that contains the 'e', could look like this:

The cells at the two ends that contain blank characters might or might not be there. Conceptually, the tape contains an infinite number of blanks in both directions, but those blanks don't have to be represented explicitly in the linked 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 left end of the list before moving. Similarly, for the right end of the list. A newly created node should contain the blank character, ' '. (Note: the blank character is written in Java as a space between two single quotes; there has to be a character between the two single quotes, even if it's a blank.)

To work with the rest of the program, the methods in the Tape class should perform as follows:

• public Tape() -- The constructor should create a tape that is initially completely blank. (It will be easiest if you represent the blank tape as a list with one node. That node would contain a blank character. Representing an empty tape by a list with one blank node will make some of the methods in the class easier to implement, since you won't have to deal with the possibility that the current cell pointer is null.)
• public char getCurrentChar() -- A trivial method that returns the char from 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 whether to move the current cell pointer to the left or to the right.
• public void setContents(String str) -- This method is used to provide input to the Turing machine. It should replace the current doubly-linked list with an entirely new list that contains all the characters from the string str, one to a node. After creating the new list, the current cell pointer should point to the last node of the list, 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() -- 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. You should not include any leading or trailing blank characters. For example, you could collect all the characters, including blanks, into a string str, then return str.trim() as the value of the method. Calling this method should not modify the tape, and it should not move the current cell pointer. (Hint: Start by moving a runner from the current cell to the left end of the list, then move it to the right end of the list, collecting characters as you go.)

The last three methods are not trivial to write! You will have to think carefully about what you want to do with the list, especially when you need to add new nodes. Draw some pictures! It is especially important when constructing the list that all the pointers are set up correctly. Remember that you need pointers pointing in both directions!

Once you have the class written, you can test it by running the programs TestTape and TestTuringMachine in the package turing.test. These programs might help you to discover errors in your implementation. You can also run the actual Turing Machine program, which is called TuringMachineGUI and is in the package turing.

The file Tape.java does not have any Javadoc comments. You should add comments before you submit your work.