Interactive Turing machines
I have put together a few interactive Turing machine examples. Each page shows the tape, an instruction table, and a state diagram. You can change the input, advance one step at a time, play the machine slowly, or step backward to see how the computation unfolds.
- 00: Unary add one — Scan to the end of a string of ones and append another one.
- 01: Binary add one — Add one to a binary number, carrying through trailing ones.
- 02: Binary addition — Add two binary numbers on a single tape.
- 03: Binary subtract one — Subtract one from a binary number, borrowing as needed.
- 04: Universal unary add one — Watch a single-tape interpreter execute an encoded unary add-one program, with the program and data stored on the same tape.
The first example is a place to start: its two rules show how a computation can emerge from reading a symbol, writing a symbol, and moving the head. The later examples build up to a machine that reads its instructions from the tape itself.