Counting Program:

Base-Two:

People count in base-ten. Computers count in base-two. In base-ten we have the one place, ten’s place, one-hundred’s place (1, 10, 100, 1000) and so on. It is just 10 raised to the zero power, first power, second power, etc… Base-two, or binary, is just 2 raise to the zero power, first power, second power, etc… So, we get 1, 2, 4, 8, 16 instead of 1, 10, 100, 1000.

How Counting Works:

Technically, we only need two binary states for a Turing machine to count. The “0” state has three rules that do not change the tape. The rules only move the tape head to the right most cell without ever changing the tape. When the “blank” cell is found, the tape head moves back one cell to the left and changes the state to “1”. Note that in the CTM, we need a state for the “blank” cell.

State “1” is used for counting and like state “0”, there are three rules. These rules are used for adding and carrying. State “1” occurs after the tape head has reached the “blank” cell and is currently on the right most digit (or bit, if it is easier to think of). While in state “1”, if the tape head reads a 0, it writes a one, carries nothing since there is nothing to carry and flips back into state “0”. The tape head moves to the right, where it reads the “blank” cell, flips back into state “1”, and moves left. But this time, it will read the 1 that it wrote on the previous pass.

If the tape head reads a 1 while in state “1”, the 1 is changed to a 0 and now the 1 needs to be carried one digit (or bit) to the left. The second rule of state “1” is responsible for the carry of the 1 to the left digit. The rule moves the 1 to the left and remains in state “1”. The machine will continue to carry in state “1” until it comes across another 0 or “blank” cell. The third rule of state “1” treats “blank” cells like zeros by changing them to a one.

8-bit Counting:

Counting Program:

State: Read: New State: Write: Move:

0 1 0 0 Right

0 0 0 0 Right

0 B 1 B Left

State: Read: New State: Write: Move:

1 0 0 1 Right

1 1 1 0 Left

1 B 0 1 Halt