Computation and Cognition - Fall 2006

Homework 7

Due by class time Wednesday, November 1

Reading

Turing Machines

Study the code for the Python Turing machine simulator we developed in class this week. Try out the simulator on the machine descriptions inverter.tm, eraser.tm, palindrome.tm, copier.tm, and welcome.tm. For example, you can run Inverter on the input string "000111" as shown below. The underscore symbols represent blanks on the tape, to give the machine some extra room to work.

inverter = loadTM("inverter.tm")
utm(inverter, "000111____")

According to A. K. Dewdney, Turing machines, running back and forth along their tapes, reading a symbol here and writing a symbol there, are a little like beavers who busily ply the waters between forest and dam, carrying sticks and branches to and fro. Just how busy can a Turing machine be? Some Turing machines are infinitely busy, in the sense that they never halt, and many of those that do halt may be made arbitrarily busy for long periods by increasing the complexity of their input. A more interesting question is how busy can a machine be when given just a blank tape to begin with? That is, in the absence of external input, must the machine have a complex internal structure in order for it to produce complex behavior? The Busy Beaver problem asks: what is the maximum number of 1's that any Turing machine with N internal states can print on an initially blank tape before halting? You might think that Turing machines with only a few internal states aren't complicated enough to print out very many 1's before they halt. Let's investigate the problem by simulating busy beaver machines with our UTM program.

  1. Run the simulator on Copier with an input string of "11000q" containing no extra blank (underscore) symbols, and observe what happens. As soon as the machine runs out of tape, the program crashes because the headPosition variable is no longer within a valid range. One way to avoid the problem is to just include extra blanks on the initial tape, so that there is enough room to hold a copy of the input string. To simulate busy beavers, however, we need to fix this problem, because we don't know in advance how much tape a machine will end up using before it halts. We need a way of automatically adding more blanks to a tape if the machine tries to move off the end of it.

  2. Write a function called expandRight(tape) that takes a list of symbols as input, representing the tape, and returns a new list twice as long containing the symbols of the original tape followed by blanks (underscores). For example:

    expandRight(['a', 'b', 'c']) should return the list ['a', 'b', 'c', '_', '_', '_'].

    Next, add the lines below to the UTM in the appropriate place. This checks to see if the tape head is about to move off the right end of the tape, and if so replaces the tape with an expanded version.

    if headPosition == len(tape) - 1:
       tape = expandRight(tape)
    

    Test the UTM to make sure it works by running it on Copier with the input string "11000q" as before. This time, you should see the tape expand when the read/write head moves past the q symbol.

  3. We need to do this for the left side of the tape as well. Write a function called expandLeft(tape) that works like expandRight, except that it adds blanks to the tape on the left side instead of the right side:

    expandLeft(['a', 'b', 'c']) should return the list ['_', '_', '_', 'a', 'b', 'c'].

  4. Modify the UTM so that attempting to move off the left end of the tape automatically doubles the size of the tape first. This is slightly trickier than the right-side case, because you can't compute the new head position by just subtracting one (which would give a negative value). Instead, the head should point to the middle of the newly expanded tape.

    Test your code on the machine busy3.tm, which is a 3-state busy beaver. When started on an initial string of five blanks "_____", it moves one cell to the right, then one cell to the left, then one more cell to the left. At this point, you should see the tape expand to the left. The machine should halt after another 10 steps. Make sure your UTM program works correctly on this machine before going on.

    You should also try out christmasTree.tm and zigzag.tm at this point. These machines go into infinite loops and thus never halt, but they do produce interesting patterns as their tape head weaves its way back and forth across the tape. To interrupt execution in IDLE, just type Control-C.

  5. How many 1's does Busy3 leave behind on its tape after halting? As it turns out, Busy3 prints out the maximum number of 1's possible for a three-state machine. The corresponding values for a few other machine sizes are given below:

    Number of states (N)    Max possible 1's printable
           1                           1
           2                           4
           3                           ?
           4                          13
           5                           ?
    

    From the table, it seems like machines with only a few states are only capable of printing out a few 1's. However, machines with only five internal states can exhibit very complicated behavior. Try out the machine busy5a.tm, which is a five-state busy beaver. This machine runs for a very long time before halting! To find out just how long, add a counter variable to the UTM to count the number of steps and have it print out this value upon halting. It will help to temporarily comment out the printTape(tape, headPosition) line to speed up execution. How many steps does Busy5a take?

  6. Next, let's find out how many 1's are left behind on the tape. There are too many to count by hand, so write a function countOnes(tape) to do the work for you and have the UTM report the final number of 1's on the tape when it halts. For example:

    countOnes(['0', '1', '1', '0', '1', '0', '0', '_', '_']) should return 3

    How many 1's does Busy5a leave behind? Compare this to the other values in the table above.

  7. The machine busy5b.tm is also a five-state busy beaver. This one takes many more steps than Busy5a to halt, although it doesn't leave behind quite as many 1's. Find out how many steps it does take (warning: be patient!), and how many 1's it leaves behind.

    Incidentally, consider the mathematical functions ones(N) and steps(N), which tell you the maximum possible number of 1's printable by any Turing machine with N states, and the corresponding number of steps required. The table in part 5 above showed the first few values of ones(N). These are examples of provably uncomputable functions, in the sense that no computer program could ever be written, even in principle, to correctly compute the values of ones(N) and steps(N) for all possible N.

Turning in Your Homework

  1. Submit your improved UTM code using the Homework Upload Site.

  2. In addition, turn in a printout of your code to me during class. Write your answers to parts 5-7 on your printout.

If you have questions about anything, don't hesitate to ask!