This lab is a little longer than previous assignments but not particularly difficult. You will use the code you write in this assignment in the next assignment.
As all of you recall from your introductory course in automata theory :-), a "Turing machine" (named for Alan Turing, one of the pioneers of computer science) is a simplified idealization of a computer. A Turing machine consists of:
An infinitely long tape divided into discrete cells. Symbols from a finite alphabet can be written into a cell. We will use the "alphabet" consisting of the numbers 0 and 1 only. There will be no other symbols in our alphabet. We will assume that the tape is infinite in both directions (i.e. there is no starting cell on the tape). All cells will start off having the number 0. Note that our Turing machine simulator will have a finite-sized tape for obvious reasons.
A "machine" which has a read/write head which is positioned at a given cell on the tape.
A finite set of states,and rules for transitioning between states, for moving along the tape, and for reading/writing to the tape. This is the "program" of the machine.
The machine starts in a given state (the "start state", which in our case will be state 0). It reads the contents of the cell upon which the read/write head is positioned and, based on the contents of the cell, performs these actions:
A symbol is written to the cell. In our case, this means that we write either 0 or 1 to the cell.
The read/write head of the machine will move one cell to the right or to the left. It cannot stay in the same location.
The machine will transition into a new state (which can be the same as the state it started in). There is one special state called the "halt state"; if the machine transitions into that state the program's execution terminates.
The result of the computation is the pattern of symbols on the tape after the termination of the program.
Turing machines are an interesting subject for many reasons, but we will be focusing on one particular problem: the search for "busy beaver" Turing machines. A busy beaver is a Turing machine which starts with a blank tape, prints a maximal number of 1s to the tape and then halts. By "maximal" we mean that no other Turing machine with the same number of states can print more 1s to the tape and then halt. The 1s produced by the Turing machine do not have to be contiguous. It turns out that it is extremely difficult to discover the busy beaver Turing machine given the number of states; in fact, as of this writing the 5-state busy beaver Turing machine is unknown! Finding it will be your job ;-) The number of 1s produced by busy beaver Turing machines as a function of the number of states is a simple example of what is called a "noncomputable function"; for more details see any good theoretical computer science textbook. Also note that there are other interesting kinds of Turing machines related to the busy beaver; my personal favorite is the "scientist" which makes a maximal number of state transitions (analogous to "working in the lab") without printing any 1s (analogous to "making significant discoveries") whatsoever before halting (analogous to "getting tenure").
You will write a Turing machine simulator which can be used to look for n-state busy beaver Turing machines. We are supplying you with template code which sets out the methods you have to write; all you have to do is fill in the gaps. These correspond to all occurrences of the word "TODO" in the method bodies (remove the "TODO" comments, of course). We've also supplied you with a variety of exception classes which should be raised on various errors. When you do this, make sure you pass a meaningful error message to the exception class constructor describing the specific problem that gave rise to the error (e.g. the Turing machine ran off the tape, or whatever is appropriate).
In brief, your program must:
Simulate a Turing machine until completion.
Raise an exception if the simulation runs off the tape.
Raise an exception if no progress is being made over a significant number of steps. This is tricky to do well! We recommend keeping a running count of the number of 1s written to the tape and the maximum number ever written and periodically (e.g. every 10000 steps) check to see if the current count is less than the maximum. If so, abort. A more stringent test would be to require that the number of 1s increases by at least some fixed amount every time you check for progress (the amount of the increase can be a parameter of the update function). Note that this progress checking will be critical to the success of lab 7, which relies on this code. For that lab, the more stringent checking will be essential to allow the program to complete in a reasonable amount of time. For this lab, don't be too stringent or you won't get the results we want (see below).
Be able to save a Turing machine representation to a file, and to load
a file into a newly-created Turing machine to set its parameters. Make
sure that your "save
" method creates a file that can then be
loaded in using your "load
" method (we will check
this).
Be able to print out the contents of the machine and the contents of the tape in an easy-to-read format.
Be able to check the contents of the Turing machine for validity.
Be able to generate random (valid) Turing machines. By valid we mean that they can't try to move to an invalid state, they can't write an invalid symbol to the tape, and they must have a single halt state that can be reached in only one way (i.e. from one particular machine state when reading one particular value from the tape).
The template code contains the docstrings for the methods used. Some of these contain suggestions for the internal representation of the machine. You can modify these if you like, and you can add other functions or methods as you see fit.
Note also that since we can't simulate an infinitely long tape, you should build a long finite-sized tape and start in the middle of the tape. In principle, you could dynamically expand the tape as needed, but we won't do that here. DO NOT implement a wraparound scheme (i.e. where a Turing Machine that runs off one end of the tape reappears on the other end); instead, raise an exception if your Turing machine goes off the end of the tape. (Question: why is it important to not use a wraparound scheme?)
Your program should print out the final number of 1's printed on the tape at the end of the simulation run. You may also have it print out information during the run of the tape (e.g. how many steps have been taken so far; don't do this more frequently than every 1000 steps or your program will take forever to run). The run function should also have a "silent" mode where it doesn't print out any information; this will be useful for next week's assignment.
Make sure you test the arguments to the BusyBeaver
constructor for validity, both in terms of their types and their ranges. If
the contents
argument (representing data needed to initialize a
particular Turing machine) is supplied, you should test it exhaustively to
see if it represents a valid Turing machine before assigning it to a field of
the class. If it's not valid, raise an InvalidTuringMachine
exception.
If you find yourself struggling too much with any part of this assignment
(or any CS 11 python track assignment, for that matter), you're probably not
aware of certain library functions that can make your life a lot easier. In
cases like this, you need to get into the habit of browsing the python
library documentation (see the python web site if you don't know where to
find it).
For instance, when loading up the input Turing machine from a file in the
load()
method, you are going to want to use the
split()
method on strings e.g.
>>> s = "this is a string" >>> s.split() ['this', 'is', 'a', 'string']
This splits a string on whitespace (spaces and tabs) and returns a list of
the parts of the string without the whitespace. Note that this doesn't
change the original string s
; it just returns a list made out of
the components of s
. When you use this method, there is no need
for complicated parsing code at all.
We are also supplying you with a file that represents the best candidate for a 5-state busy beaver Turing machine discovered to date. Your program should load this in, simulate the Turing machine and print out the total number of 1s printed to the tape. It should be exactly 4098. The testing code is included at the end of the template code; do not modify it.
Here is the template code.
Here is the file to read in.
Each line in the file represents a state of the machine; the first line corresponds to state 0 (i.e. the machine uses this information if it's currently in state 0), the next state 1, etc. States are numbered from 0 to 4, giving 5 states in all. The first three numbers/letters on each line represent the actions to be taken if a "0" is read on the current cell of the tape, while the latter three represent the actions to be taken if a "1" is read. The three numbers/letters represent:
and similarly for the last three numbers. When you load this file in,
you'll have to convert it into your program's representation of a Turing
machine state transition table (in the load()
method).