Python track: lab 7: fun with genetic algorithms

For this lab, we will use the code developed in lab 6 to search for Busy Beaver Turing machines using genetic algorithms, which are an interesting kind of search technique often used for difficult problems with no obvious structure we can exploit.

Note that the amount of code you need to write for this lab is relatively small, but it will take a while to explain the problem fully, so read the lab carefully before beginning.

The task at hand

In assignment 6 you wrote a program to simulate a 5-state Turing machine, and you used that program to verify that a particular such Turing machine would print out 4098 1's before halting. A "busy beaver" 5-state Turing machine is one that will print out more 1's starting from a blank tape than any other 5-state Turing machine. It is not known whether the Turing machine you simulated is in fact the 5-state busy beaver. An obvious question is: can we find a better one? Or, alternatively, what's the best one we can find assuming we had no prior knowledge? We have to search through the space of 5-state Turing machines to find one that can print out the largest number of 1s and then stop. How many such Turing machines are there? For each of five states, we could be reading either a 0 or a 1 on the tape, and in either case we could write either a 0 or a 1, move left or right, and transition to one of six states (the five states plus the halt state). This makes for (2x2x6)^(5x2) = 63,403,380,965,376 different TMs. Another complication is this: given that we use a finite-sized tape, if the TM runs off the tape, how do we know that it wouldn't have halted eventually if we had a longer tape? Well, we don't, so we just have to see how well we can do given these limitations. If we could test a new TM each microsecond, and we didn't have to worry about running off the tape, we could search through all the TMs in about 64,000,000 seconds, or 740 days. Of course, we don't have that long, so we'll try to do something more clever, which may or may not work well.

Genetic algorithms

A genetic algorithm (GA) is an algorithm for searching a large space of possible configurations (called a parameter space) of some computational process (here, 5-state Turing machines). The idea is to encode the numbers that determine the configuration and then look for the best set of numbers (the set of numbers is referred to as a parameter set). In our case, these numbers would determine the structure of 5-state Turing machines. There are different ways to encode these numbers; we'll talk about this more below. Assuming that we have such an encoding, we can generate a large population of random Turing machines and simulate each one to see how many 1s it produces starting from an empty tape. This number can be used to determine the "fitness" of each Turing machine; we'll talk about this below as well. The fitness is a measure of how good the parameter set is; higher fitness means a better parameter set.

Once we have determined the fitness of each parameter set in the population, we can generate a new parameter set that is likely to contain some Turing machines that are better than the best ones in the current population by using a genetic algorithm. This algorithm consists of three stages:

  1. Take the most fit members of the current population and generate a new population (which is the next generation of parameter sets) according to some rule. We will use a rule called "fitness-proportional reproduction". Each of the parameter sets in the new generation is initially identical to one of the parameter sets in the old generation.

  2. Take some of the parameter sets, pair them with other parameter sets and perform an operation called "crossing-over" which generates a new pair of parameter sets from a pre-existing pair. The process takes chunks of the two parameter sets and generates new parameter sets that consist of part of the first one and part of the second one.

  3. Go through each parameter in each of the parameter sets and implement mutation of the parameter with some low probability.

These three processes occur in the order just described. All three of these processes are described in more detail below. The genetic algorithm gets its name because the three steps are roughly analogous to biological genetics (selective breeding, recombination or crossing-over, and mutation). Note that there are a very large number of ways to implement all three of these processes; the implementations we will use will be very simple and straightforward but not necessarily optimal. Note also that genetic algorithms are not guaranteed to find the optimal solution to the problem (unless you have infinite time to run the simulations, in which case anything will work); it turns out that some problems work very well with GAs and others don't work as well. We will see how well they work when we use them to find busy-beaver Turing machines (hint: don't get your hopes up).

Encoding the Turing machine state

To encode a five-state Turing machine, we use ten "slots". Each slot corresponds to the actions to take when in a particular state (0-4) looking at a particular number on the tape (0 or 1). Each slot consists of a tuple of length 3, which includes:

  1. The value to write on the tape (0 or 1)
  2. The direction to move (left or right, which we encode as 0 or 1)
  3. The state to transition to (0-4, or -1 for the halt state). Note that we use 0-based indexing for the state indices as usual.

Each parameter set is a list of these tuples; the list is exactly ten tuples long. Our initial population is a list of these parameter sets, which is therefore a list of list of tuples. The contents of the tuples of the parameter sets are selected randomly from valid values (e.g. the value to write is either 0 or 1, the direction to move is 0 or 1, and the state to transition to is an integer between -1 and 4).

The fitness function

The fitness function you will use is very simple: just simulate the Turing machine and add 1 to the total number of 1s written on the tape when the Turing machine halts. If it doesn't halt, runs off the tape, or fails in some other way, give it a fitness of 1. You might wonder why we don't just use the number of 1s directly instead of adding 1. This is to avoid difficulties in the unlikely event that all the Turing machines had a fitness of zero; this would cause division-by-zero errors in our reproduction algorithm (see below).


We implement reproduction as follows.

  1. We compute the fitness for each parameter set.

  2. We create a new array (list) to store the new parameter sets which is the same size as the old array.

  3. We take the very best parameter set and copy it to the first location in the array. This parameter set will not be altered at all in this location.

  4. We add up all the fitnesses (including the best one) and determine what proportion of the total number of remaining available locations in the parameter sets array is represented by each parameter set (including the best one). Then we round this to an integral number for each parameter set and copy that number of each parameter set to the new array. There are different ways to do this, and it's not necessary to be absolutely precise, but each location in the new array should have a parameter set in it and more fit parameter sets should be copied into more locations than less fit sets. NOTE: Make sure that you copy each parameter set and don't just copy a reference to it. This is the single most common bug in this lab.


Pairs of parameter sets are selected at random and each member of the pair is crossed over at one location (which is randomly selected for each pair). This means that two old parameter sets become two new ones as follows:


        1: A B C D E F G H I J
        2: a b c d e f g h i j


        1: A B C D e f g h i j
        2: a b c d E F G H I J

where A-J and a-j represent parameter slots in order. In this case the crossover occurred at the position between slots C and D (c and d) of both sets. The location of a crossover is random but must be between two slots in a parameter set. There is a number called a "crossover probability" (p_crossover) which determines how many parameter sets in the population get crossed over:

    n_pairs = int(p_crossover * (nsets - 1) / 2)

Choose pairs so that once a given pair has been crossed over, it won't be chosen again (sampling without replacement). Also, make sure that your crossover location actually does something e.g. don't cross over at location 0. Also, do not alter the best parameter set that is in the first location when doing crossovers.

You may find the random.shuffle() function to be useful. Type   pydoc random   for more information on it.


Each parameter slot in each parameter set (except for the first one, which we leave alone) should be mutated with some low probability. What this means is that for each location in each parameter slot (there are three of these, representing the number to write on the tape, the direction to move in, and the state to change to), a random number is generated and if it's below a threshold (called the mutation probability), the contents of the location are altered randomly. For instance, if the number to write on the tape is mutated, you could change it from 0 to 1 or vice versa; if the direction is to be mutated, you could change it from left to right or vice-versa, and if the state to transition to is to be mutated, you could choose it randomly from the range -1 to 4.

Program to write

We're supplying you with these files:

Much of the code is supplied for you, but both of these files are incomplete; you will have to fill in the methods with comments marked TODO (remove the TODO comments, of course). Don't modify any of the other methods at all. Make your method implementations conform to the docstring comments for each method. You will also need the program you wrote for assignment 6. The file is self-contained and can be tested independently of either of the other files. The reason for this is that all of the aspects of the genetic algorithm that are specific to the busy beaver problem are passed to the GA code as arguments to the GA constructor. These arguments are functions which handle initialization, mutation, evaluation and saving of parameter sets. (Note that it's perfectly legal in python to pass a function as an argument to another function, just like it is in languages like Lisp or Scheme.) Most of this code has been provided in for the busy beaver problem. For testing the GA code, though, we've supplied a simple (perfectly solvable) test problem at the end of which can be invoked by typing

% python

once the other parts of the GA code are filled in. You should make sure that this works before trying to run the GA on the busy beaver problem. If your GA code cannot perfectly solve the test problem there is probably something wrong with your code (try it a few times; it runs for ten generations only so it may not work every time).

When searching for busy beavers, you should run your busy beaver simulation code from lab 6 in silent mode so as not to clutter up the output with a lot of irrelevant printouts (modify the lab 6 code if necessary).

Running the program

Once your GA class works correctly and you've written the necessary code in you're ready to search for busy beavers. Type python and away you'll go. I recommend you try to run the program for at least an hour (you may want to run it late at night when the CS cluster computers are less heavily loaded). Every generation, save the best TM found so far to a file (the code supplied does this automatically). The name of the file should be best.<n> where <n> is the generation number. You should also include a file which includes some sample output from the GA program as it searches for busy beavers, as well as another file which gives the best BB TM you found along with the number of 1s it outputs. To save the sample output file for the program as it's running, run it like this:

% python | tee bb_search.out

which will print out the results of the program to the terminal while simultaneously saving them to the file bb_search.out. Halt the program whenever you get tired of it, but let it go at least ten generations. Note that by default, python will only search for ten generations and then halt; if you want to search for longer give an integer command line argument. If it's negative, the program will run until you halt it; if it's positive, it will run that many generations.

NOTE: Once your program is finished, it must be possible to independently check how many 1s the best Turing machine produced. The easiest way to test this is to copy the Turing machine's description file to a file called "" (just like in lab 6) and run "python". If this fails for any reason, the lab will have to be redone. Make sure that you don't break your old busy beaver code while changing it for this program! This should be obvious, but for some reason, it isn't.

The best busy beaver found by my program so far produced only 21 1s before stopping. Hopefully your program will do better. You can try altering the mutation and/or crossover probabilities to see if that will help. One interesting feature is that the algorithm almost invariably picks out Turing machines that have only one halt state, even without being specifically programmed to do so. Such is the power of (un)natural selection.

Things to watch out for


Every year, most of the lab 7 submissions are broken in some way, and have to be redone. The reasons are usually trivial and easily fixed.

What to hand in

The files,, and your (possibly modified) code from lab 6.