The central metaphor of Cognitive Science is that cognition can be viewed as a form of computation. A Turing Machine is a theoretical model of a computer. It can simulate any abstract computation, such as another Turing Machine, and is therefore considered to be universal. In this lab we will experiment with a Turing Machine simulator and write our own simple machines to gain a better understanding of what constitutes computation.
It is important to understand the mechanisms of a Turing Machine because there are a number of philosophical arguments that are based on this formalism. For example, the Church-Turing thesis is the hypothesis that anything that can be computed can be computed by a Turing Machine. In other words, a Turing Machine captures all of the essential aspects of computation. Furthermore, Alan Turing speculated that any problem that can be solved by a human can, in principle, also be computed by a Turing Machine.
A Turing Machine consists of:
A program on a Turing Machine consists of a series of statements made up of five parts:
Below is an example of a Turing Machine program that will read a tape containing a series of 1's and 0's and invert each number to the opposite number.
# inverter.tm # example input: 1101___ # example output: 0010___ A 0 A 1 right A 1 A 0 right A _ Halt _ right
Lines that begin with a hash mark are comments. The program itself is just three lines long. For our particular Turing Machine simulator, the machine always begins in state A. The first statement can be interpreted as: "When in state A and reading a 0, the next state will be A, write a 1 and then move to the right." The second statement can be interpreted as: "When in state A and reading a 1, the next state will be A, write a 0 and then move to the right. The final statement can be interpreted as: "When in state A and reading a blank, the next state will be Halt, write a blank and move to the right." The Halt state is a special state that always causes the machine to stop processing.
This machine overwrites every 0 with a 1 and every 1 with a 0 and when it reaches a blank space on the tape it halts.
update-cogs1Initially this will create a sub-directory called cogs1. Each time you type this it will copy over any new files that I've made available for you. You can then close the terminal window.
>>> utm("inverter.tm", "1101___")This will open up the description of the inverter machine described in the previous section and will execute the machine showing you how the tape changes on each step. In the above command utm stands for Universal Turing Machine, "inverter.tm" is the name of the file that contains the inverter machine statements, and "1101___" is the description of what is on the tape. Try executing this same machine with a different set of inputs on the tape.
>>> utm("inverter.tm", "00010___")
>>> utm("eraser.tm", "100010___")
You should do all of the work for this lab in the directory cogs1/labs/1. When you are ready to turn in your work, open a terminal window and type:
handin-cogs1This will make a copy of your directory. You can run the handin program multiple times before the due date, but once the deadline passes the handin program will no longer be available. Each time you run handin, the latest versions of your solutions will be copied over to me.
""" This is a long comment. I can put in as many lines as necessary. And here's more. And even more. """Will this subtraction machine work in all cases? If not, what cases are problematic? Explain your answers to these questions in your comments as well.