CPSC 120: Principles of Computer Science, Spring 2002
Lab 6: Turing Machines
THE TOPIC FOR THIS LAB is Turing Machines, which are covered in Chapter 4 of the textbook. The basic information in the lab can be found in the lab worksheet
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
Since you will need to save your work, you should run the lab examples by running the RunLabs program (either under Linux, from the directory /home/cs120 directory or under Windows, from the cpsc120 directory on the PCCommon drive). When you run this program, click on the "xTuringMachine Lab" button. You need to use the RunLabs program to get the examples that are mentioned in the Lab worksheet. Do not do the exercises on the lab worksheet (except for practice, general interest, or fun). The exercises that you should turn in are given later on this page.
You should work through the material in the lab worksheet. However, you should do the exercises on this sheet. Save the Turing machines that you make for the exercises in your homework directory. Please name them TM1, TM2, TM3, and TM4, or else make it very clear in your lab report how the files are named. The lab report is due in class next Wednesday, February 27.
Exercises to Turn In
Exercise 1: Create a Turing machine that will move to the right until it finds the string xyz in three consecutive cells on the tape. If it finds this string, it should halt, and when it halts it should be on the square containing the z. If it never finds the string, it should never halt. (The idea behind this machine is similar to the "FindDoubleX" example.) In a short essay, answer the following questions: What is the meaning of each state in your machine? That is, what purpose does it serve in the computation or what information does it represent? How many states would you need in a machine whose job is to search to the right for the string xyzxyz ? Why?
Exercise 2: One of the sample Turing machines can add 1 to a binary number. Create a Turing machine that will add 2 to a binary number. Like the "Add-1" machine, your "Add-2" machine should be started on the rightmost digit in a string of 0's and 1's. If you are given some particular integer, N, how could you build a Turing machine that adds N to its input?
Exercise 3: Create a Turing machine that removes the y's from a string of x's and y's. When the Turing machine starts, the tape contains a string of x's and y's, and the machine is on the left end of that string. When it ends, the tape should contain a sting of x's, with no y's, in which the number of x's is the same as the number of x's in the original string. The output string does not have to be in the same place as the input string. You can get some ideas from the CopyXYZ example, except that you should only copy x's, not y's, and you should erase the original string. Write a paragraph to describe the procedure that your machine uses to solve the problem.
Exercise 4: Create a Turing machine that does the following: It will be started on a tape that contains a string of one or more $'s, and when it starts it will be on the leftmost $ in this string. When the machine stops, the $'s will be gone and the tape will contain a binary number (that is, a string of 0's and 1's). The binary number will be give the number of $'s that were in the original string. One way to organize the computation is: Write the binary number in the cells to the left of the the $'s. Begin by writing a 0 there. Then move to the right end of the string of $'s, and erase the last $. Move back to the binary number and add 1 to it. Repeat the process until all the $'s are gone.
Exercise 5: I have claimed that Turing machines can do any computation that can be done by any computer. What is your reaction to this claim? Do you believe it? What evidence is there to support this claim? What reasons might someone have for doubting it? Write a short essay discussing your answers to these questions.
--David Eck (eck@hws.edu), 22 February 2002