*Analogies and Metaphors to Explain Gödel's Theorem*by Douglas Hofstadter (supplementary reading #8)*Conversations with Gödel*by Rudy Rucker (supplementary reading #9)

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.

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.Write a function called

**expandRight(**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:*tape*)`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.We need to do this for the left side of the tape as well. Write a function called

**expandLeft(**that works like expandRight, except that it adds blanks to the tape on the*tape*)*left*side instead of the right side:`expandLeft(['a', 'b', 'c'])`should return the list`['_', '_', '_', 'a', 'b', 'c']`.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.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?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(**to do the work for you and have the UTM report the final number of*tape*)**1**'s on the tape when it halts. For example:`countOnes(['0', '1', '1', '0', '1', '0', '0', '_', '_'])`should return 3How many

**1**'s does Busy5a leave behind? Compare this to the other values in the table above.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*.

Submit your improved UTM code using the Homework Upload Site.

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!