Turing Machines

A Turing Machine is a hypothetical computer invented by Alan Turing. It consists of an infinite tape on which symbols may be read and written. The machine travels right or left along the tape. At each step the machine writes to the tape, travels either left or right and changes state. The set of symbols and the set of states are both finite sets.

Inverter

Click on the box to activate the Turing Machine.

The Turing Machine shown is an inverter - it travels along the tape turning 0's into 1's and 1's into 0's. This is achieved with only one state and two symbols plus blank.

A Turing Machine can be described by a function with two inputs and three outputs. The function for the inverter is as follows:

INPUTSOUTPUTS
state symbol symboldirectionstate
x01Rx
x10Rx

Note that the function is undefined when a blank symbol is read. Under these circumstances the Turing Machine simply stops.

Some Turing Machine problems. Try the tutorial which asks for the following: