Due: Thursday 30 October, 6:00 pm
This assignment is worth 10 marks towards your grade in this course.
Turing Machines
A Turing Machine is a simple mathematical model
of a computer.
It has a tape that extends forever in either direction, and each cell
of the tape contains a 1, a 0, or a blank.
The tape has a read/write head which can look at one cell at a time.
A Turing Machine program is a finite sequence of instructions.
Each instruction has a unique line number; line numbers need not start
at 1 or be consecutive. Execution begins at the first instruction.
Below are the valid instructions:
We have written a Java applet that simulates the operation of a Turing Machine.
The course web page contains a link to the applet.
Run the applet to get a sense for how Turing Machines work, and how
one can solve interesting problems using such a simple language.
A Turing Machine is an abstraction.
We don't generally implement Turing Machines
as physical devices or in any other way. Instead, we use them to
reason about computation.
For example, the famous Church-Turing thesis says that
any problem solvable by an algorithm can be solved by
a Turing Machine program.
Turing Machines have also been used to show that certain problems
cannot be solved by any program written in any language.
This is quite a remarkable sort of statement!
You can learn more about Turing Machines and related topics by taking
CSC448.
Your task
Your task is to write one of the classes needed by our Turing Machine
simulator: class ListWithCurrent.
This class maintains a sequence of Objects, and a ``current'' object
within the list. Operations include inserting at the front of
the list, the back of the list, or at the current position;
deleting the current object;
and advancing the current position (moving it forward)
or retracting it (moving it backwards).
The ListWithCurrent class is used in two places in our Turing Machine
simulator. The input tape is represented, in a class called Tape,
as a ListWithCurrent. The current is used to keep track of where
the read/write head is located. The Turing Machine program itself
is also represented
as a ListWithCurrent. In this case, the current is used to keep
track of which instruction is currently being executed. Most instructions
advance this current by one instruction, but a goto instruction moves
it to the appropriately numbered instruction.
Notice that one class, ListWithCurrent,
has been put to use in two very different ways.
This is possible because we designed the class to be as general as possible;
it has nothing in it that is specific either to Turing Machine tapes or
Turing Machine programs.
You must implement ListWithCurrent using a doubly-linked list of
Objects.
Through
the course web page,
we will provide an outline for the class
ListWithCurrent, including the header for every public
method.
This starter code defines the interface to the class, and you must not alter it.
Many of the methods in the class are used by our simulator, and for each of those
we will provide very careful comments and preconditions so that you
can know what is required of you when you fill them in.
Other methods are not used by our simulator, but are required for
the sake of completeness. (Remember that we wish to design classes that
are general and thus will be likely reused in other programs.)
For each of these methods, we will provide a loose description of their purpose
and you will be required to turn this into more precise comments and
preconditions.
In some cases, there may be several different specifications that
you could come up with that fill out our loose description. Any one
will be accepted, as long as it is precise.
For some of the methods that you complete, you will find it convenient
to write helper methods. Do so as appropriate for good program design.
We will not provide you with the code for our simulator.
As long as our specifications for the ListWithCurrent class are
clear, it will be possible to implement the class in complete ignorance
of the code that uses it.
Of course, if you find something in the specifications unclear, let us
know.
Testing your class
You are to test your class in two ways. First, you must convince yourself
that it works in the context of our Turing Machine simulator.
This is called ``integration testing'' (see Standish, appendix C.5).
To do this, make your own copy of the class files for the
simulator (instructions for how to do this
will be posted on the course web page).
These class files will contain all of the code except the ListWithCurrent
class.
Then compile your own version of ListWithCurrent
and run the program.
The simulator is an applet,
so in order to run it, you'll need an html file that calls the applet
and provides it with inputs. Such a file will be provided on our web page.
Your integration testing will not be completely thorough,
partly because the simulator doesn't use all public methods in the
ListWithCurrent class, and partly because our html page
will only make a couple of calls to the simulator applet.
Still, this testing may reveal some problems in your class. If so, debug
and fix the problems.
The second sort of testing will be very thorough ``unit testing''
of your class (see also Standish, appendix C.5).
Write a ``driver program'' - a program
that allows you to test each method within the class.
This can either be a general driver that prompts you for test cases to try,
or it can have specific test cases ``hard coded'' into it, so that
it tests exactly the same cases each time it is run.
Either approach is fine.
What to hand in