Cogs1 Spring 2007
Lab 1: Turing Machines
Due by 11:30pm on Wednesday, February 7


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:

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.

# 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

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:

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

  1. Simulate the machine 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 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.