Now and then someone one has an idea that changes the world. Plato had several world-making thoughts and theories, as did Descartes, Copernicus, Darwin, Freud, Marx ... -- you can add to this list as you like, and probably you and your classmates could agree on the main figures who have revolutionized thinking, at least in the Western tradition. But someone who might not appear on that list is Alan Turing. Over the next two labs, however, we will explore the deep influence that Turing’s way of thinking has had, an influence that is yet to peak.

Turing’s work was focused in mathematics, but one of his ideas has spilled out of mathematics into the practical world of computers. That is the idea for a simple computing machine, which has since been called a "Turing Machine." A Turing Machine is not a real physical machine, but rather an abstract model of a simple computing device. As you will learn, it is not so much a machine as a way of thinking. And, ultimately, it is a way of thinking about thinking, a way of thinking about the mind.

As a prerequisite to this lab, be sure to read Haugeland, Chapter 4, and the handouts to accompany the program, "Turing’s World."

There is no one "Turing Machine." Instead, a Turing machine is any one of a family of machines. Turing machines are all designed to be algorithm implementers, or in Haugeland’s terms, automatic formal systems. All Turing machines share a very simple architecture, consisting of a tape, the "memory" of the machine, and a read/write head, which is capable of only the most elementary modifications of the marks on the tape. From this simple specification, all else follows. In particular, Turing proposed the powerful thesis that any process that could be specified in an algorithm could be computed on a Turing machine. Any algorithm! On such a stupid device as this!

We will use a very friendly simulation of a Turing Machine to appreciate the boldness and the beauty of Turing’s idea. The software is called "Turing’s World."

Drag the Turing’s World folder out of the Class Software window and drop it on the desktop. (Depending on your Mac, you may be asked whether you want to copy onto your hard disk. Click OK.) (You may also copy this on your own disk. Any copy you make is completely legal.)

Close the Class Software window (by clicking on the little box in the top left of the window).

You should see the Turing’s World folder.

Working with a partner is recommended. Consider and discuss the questions raised in the text . (You do not need to write out your answers.)

You can save time and increase your learning by working with a partner on this. You might discuss your response to each question, but divide the labor of writing. Just make sure that both your names are on any section that either of you hand in.

1. Design a new Turing machine. Outline a design for a machine that takes a string of As and Bs in any order and simply copies the string to another part of the tape. For example, given BABAAA, it would end with BABAAABABAAA. See if you can specify what the submachines should do, and how they might do their separate tasks. The machines discussed near the end of the handout will provide many hints about how to solve this problem.

Many of you will want to try actually writing the program to perform this function. But if this is too intimidating, simply outline, in plain English, how such a program would have to work, and leave the programming for another time.

2. Are you a Turing machine? There are, of course, a vast number of interpretations of this question, so you’ll need to figure out If so, why? If not, why not? (If your verdict is split, consider reasons on both sides of the issue.)