System Design Exercise 2: Turing Machine Programming

The Turing Machine is a theoretical model for the basis of modern computation as laid out by Alan Turing in the mid 1930s. In it's simplest form, the machine consists of the following:

The table is defined using a state diagram with each state reading the value of the current position on the tape and then performing one or a set of the available instructions in order:

  1. read the symbol at the current position of the tape
  2. erase or write a symbol at the current position on the tape
  3. move left, right, or stay in place
  4. switch to a new state within the instructions table


The exercise is to write 3 Turing Machine programs that work with binary data (1's and 0's) to solve the following problems that we'll "run" in class:

Each of your programs should consist of a state machine, either as a diagram or as a table. Your input digits are 1, 0, _ where _ denotes a space aka nothing and 1 and 0 are binary digits.


An example that prints the binary number 1010 might be:

State Read Write Move Next State
1 - 1 R 2
2 - 0 R 3
3 - 1 R 4
4 - 0 - halt

This program doesn't care about the input characters, so it doesn't read anything. Also, when the program is finished we stop it using a "halt" state. A more low level method would be to add another state that simply returns to itself without doing anything. In this case, we'll use "halt" instead.

Here's an example which replaces any two consecutive 1 digits with 00 ie. 1101011 becomes 0001000:

State Read Write Move Next State
1 0 - R 1
1 - R 2
2 0 - R 1
1 0 L 3
3 - 0 R 4
4 - 0 R 1

This program reads input characters and decides which state to go to next. The order to the states determines when to move left, move right, and replace a digit.