• Contribute
• What's New
• Submit News

Below is the simplest of Turing Machines, one that simply adds one to a number. A number is represented as a series of 0s and 1s. It is represented in a continually stream of 1s with padding zeros around them. For example, 3 is 0011100, 8 is 001111111100. The type of representation is called unary notation. The padding zeros just make it easier for the program to add, because if there is no cell to write to, it won't create one. All we need to create f(x) = x+1 are two states, arbitarily called "State A" and "State B". These are indicated below with checkboxes, the one checked is the state the machine is in.

These are the rules for the machine:

• If the internal state is "State A", and it reads a 0, output a zero.
• If the internal state is "State A", and it reads a 1, change to "State B", and write a one.
• If the internal state is "State B", and it reads a 0, change to "State A", and write a one.
• If the internal state is "State B", and it reads a 1, output a one.

A Simple Turing Machine  Input:   Output:   State A State B