Turing Machines

This activity 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.

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 Reset it.

Gaining Familiarity with Turing Machines

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 is 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.
• Turing Machine #2
  The start state of TM2 is 0. Its alphabet is the set of 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. (This is called unary number representation.) On input 111b it produces output 1111; on input 1111b it produces 11111; ... now do you see the pattern? TM2 adds one to a positive integer.

Understanding Turing Machines

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. Test the TM on your new input. Keep experimenting with different valid input strings until you see a pattern. (A useful shortcut: You can use the tab key to move from one tape cell to the next.)

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 #2 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 consists of the symbols 1, #, and b. The format for the input is two strings of 1's, separated by #, representing 2 unary numbers. The output is a single string of 1's preceded by a b. (You can ignore the b in the output; it symbolizes a "visible" blank). What is the overall effect of this TM? In other words, what is the relationship of the output to the two inputs? You should experiment with different inputs to test your hypothesis.
• Turing Machine #4
  Like the previous TM, the alphabet for this TM consists of 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 input represents two unary numbers, and the b is a "visible" blank.) The output is a single string of 1's. What is the relationship of the output to the two inputs? You should experiment with different inputs to test your hypothesis.
• Turing Machine #5
  The input format for this TM is a string of 1's followed by a b. In the output, the b is replaced by a T or F, representing True or False. What is this Turing Machine testing for? You will need to experiment with a number of inputs to see the pattern.
• Turing Machine #6
  The alphabet for this TM consists of the symbols 0, 1, and b. The format for the input is a string of 0's and 1's, followed by a b. In the output, one of the symbols is replaced by either an N or a P. What is this Turing Machine testing for? (Hint: the P stands for something. The N stands for "not a p…".) Again, you will need to experiment with a number of inputs to see the pattern. If you see the pattern but don't know the name of it, just describe the pattern as well as you can.