Introduction

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.

Overview of a Turing Machine

A Turing Machine consists of:

• An infinite tape that is divided into squares, each of which can hold one character of information.
• A read/write head that can move to the left or right on the tape.

A program on a Turing Machine consists of a series of statements made up of five parts:

1. current state
2. character being read
3. next state
4. character to write
5. action to take (move to left or right)

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.

Getting Started

• Each week I will provide you with some starting point files. To copy these files into your directory, click on the terminal icon at the bottom of your screen. Then type:

  update-cogs1
  

  Initially 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.
• Click on the icon for idle (a blue and yellow swoosh). From the menu, choose to open a file. Then click on the following: cogs1, then labs, then 1, and finally turing.py. This will open the Turing Machine simulator which is a Python program. Don't worry, you don't need to understand this code. You should now see two windows. One window is an editor containing the Turing Machine program, the other window is an interpreter where you can run the program.
• From the menu, choose to run the file. Then move your mouse over to the interpreter window with the >>> prompt.
• Now you can start simulating various Turing Machines. In the interpreter window type:

  >>> 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___")
  

• There are a number of other machines provided for you to try. To view these various machines, from the file menu choose open. Then at the bottom of the chooser window change the file types to be all text files. You should now see a number of files that end with a ".tm" extension. Each of these is another example of a Turing Machine. Open one, such as eraser.tm, and try to understand how it works. Then simulate it and see if your interpretation is correct.

  >>> utm("eraser.tm", "100010___")
  

• To exit idle, from the file menu choose to quit.

What to turn in for this lab

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-cogs1

1. Simulate the machine subtract.tm. Add a detailed comment to the end of this file to explain in your own words how it works. Show several examples of the tests you performed giving the input and the resulting output. You don't have to explain each statement of the machine, but give an overview of the solution. Multi-line comments can be inserted between triple quotes as shown below:

   """
   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.
2. Write your own machine called parity.tm. This machine should read a tape containing a series of 1's followed by blanks and determine if the number of 1's is odd or even. For example, if the input were "111___", then the output should be "111o__" where the "o" designates odd. Similarly, if the input were "11___", then the output should be "11e__" where "e" designates even. If the tape is entirely blank "___", then the output should be "e__" because zero is considered even. If you'd like to allow your machine to handle slightly more complex input, you can have it ignore any 0's it encounters. In other words, a 0 does not change the parity of the input.