Python track: lab 6: fun with noncomputable functions


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.

Turing machines

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:

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:

The result of the computation is the pattern of symbols on the tape after the termination of the program.

Busy beaver Turing machines

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").

The program

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:

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.

Tips

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.

Testing the code

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.

Files supplied