# 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
`1`

to`0`

and`0`

to`1`

so`1100`

becomes`0011`

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