Exercise 1: A Linked List of Ballistic Balls

The program ListOfBallisticBalls shows a "ball" bouncing around inside a panel. When the user clicks the panel, a new ball is created at the point where the user clicks. As the program stands now, the new ball replaces the existing ball. The exercise is to make the program use a list of balls. When the user clicks, the new ball should be added to the list, and all the balls in the list should bounce around in the panel. (Note: You should add the new ball to the head of the list, which is easy, not to the tail, which would be harder.)

You will have to introduce a list into the program. The balls in the program are represented by the nested call Ball. You want to implement a linked list of Balls. There are two ways to do this. You can add a next instance variable to the Ball class itself, or you can create a new ListNode class in which the data field is of type Ball. Other things in the program that have to be changed are marked with TODO's.

You will not have to change any of the comments on the program, except to remove the TODO's, since all the comments already talk like there is a list of balls.

(One thing you might add to the program: Instead of adding just one ball when the user clicks, add several, all spraying out from the clicked point. You might choose the number to add at random.)

I should note that, ordinarily, you would use one of the built-in classes ArrayList or LinkedList to represent the list of balls. But the point of the exercise is to implement a linked list directly, as a chain of linked nodes.

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.

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 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 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 an applet 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.

Exercise 2: 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 node will contain a single char, 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 won't need pointers to the beginning or to the end of the list. What you will need is 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, ' '. (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 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. Representing an empty tape by a list with one blank node will make some of the methods in the class easier to implement.)
• 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 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. 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(). (Hint: Move a runner from the current cell to the start of the list, then move to the other 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. 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. The actual Turing Machine program is called TuringMachineGUI, in the package turing.