Kalamazoo College

Kalamazoo, MI 49006

Turing Machines

This mini-lab is based on a lab found in Chapter 8 in *The Analytical
Engine* written by Decker and Hirschfield. It has been adapted
and written by us to help you explore the ideas of Turing Machines.
Follow these steps for the mini-lab:

The first thing to notice about our Turing Machine
Simulator is that it represents all of the
components of a Turing Machine (TM). The "Tape" is displayed
horizontally near the top of the program window, with an arrow beneath
it indicating the current position of the scanning head. The large
table contains rules, one per row, of the TM being simulated.
There are also display fields for
the "Current State" of the machine and the "Rule Used" to make the
previous move. The panel at the right of the display fields provides
a set of buttons for the basic control of the machine: you can *Step*
through a TM or *Run* it through to completion, as well as *Stop*
and *Reset* it.

Run through each of the first two Turing Machines given by clicking on the Run button. Compare the "Original Tape" to the "Ending Tape". Do you see a pattern here? Click the "Restart" button to reset the simulator, and run the Turing Machine to completion again, this time using the Step button to step through the rules one at a time. You do not need to turn anything in for Machines #1 and #2.

- Turing Machine #1.
The start state of TM1 as you saw, was 1. Its alphabet is the set of symbols 0,1 and b (which we use to stand for blank). The required format for the input tape is any combination of zeros and ones, followed by a single !, followed by a series of b's of length equal to (or greater than) the length of the leading 0's and 1's. The result? TM1 makes a copy of the zero-and-one portion of its tape at another location on the tape. While this may seem a trivial use of a TM, think of the utility of this operation to modern computers!

- Turing Machine #2.
The start state of TM2 was 1. Its alphabet is the symbols 1 and b. The required format for the tape is a number of ones followed by a b. In order to understand the processing accomplished by TM2 you need to know more than its alphabet, start state, and tape format. You need to know that the original tape is intended (by its authors) to represent the integer 3. That is, TM2 uses strings of ones to represent positive integers. On input 111b it produces tape 1111; on input 1111b it produces 11111; ... now do you see the pattern? TM2 adds one to a positive integer. This is called unary arithmetic.

Run through the two Turing Machines given below by clicking on the Run button. Compare the "Original Tape" to the "Ending Tape". Do you see a pattern here? Once you've formed a hypothesis about what the Turing Machine is doing (or if you can't decide what the TM is doing), restart the TM and change the tape input. (A useful shortcut: You can use the tab key to move from one tape cell to the next.) Test the TM on your new input. Keep experimenting with different valid input strings until you see a pattern.

For each of the Turing Machines below, write down on a piece of paper a short description of the overall behavior of the machine. For example, the behavior for Turing Machine #b above might be "Adds 1 to a unary number." Some of the machines below also use unary numbers.

- Turing Machine #3.
The alphabet for this TM is the symbols 1, !, and

*b*. The format for the input is two strings of 1's, separated by !. The output is another string of 1's preceded by a*b*. You can ignore the*b*in the output; it symbolizes a blank. (We use a*b*to represent a blank in the rules because the*b*is more obvious.) - Turing Machine #4.
The alphabet for this TM is the symbols 1, !, and

*b*. The format for the input is two strings of 1's, separated by ! and followed by a*b*. (Again, the*b*is just a more visible blank.) The output is a string of 1's.