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:
- tape: an infinite "tape" containing data, used for both input and output
- head: a read/write head which traverses the tape, reading & writing information
- state register: the current state of the machine aka "state of mind"
- table: a table of instructions indicating what to do aka the "program"
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:
- read the symbol at the current position of the tape
- erase or write a symbol at the current position on the tape
- move left, right, or stay in place
- switch to a new state within the instructions table
Exercise
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:
- print a given binary number to the tape
- invert a binary number on the tape: change
1to0and0to1so1100becomes0011 - add 1 to a binary number on the tape, the number is surrounded by spaces on the left and right: so the binary
_011_(decimal 3) becomes_100_(decimal 4)
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.
Examples
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.