Binary subtract one
Example 03The head reads one cell. Zero stays zero; leading zeros are kept.
Instruction Table
| State | Read | Write | Move | Next state |
|---|---|---|---|---|
| Check for 1 | 0 | 0 | Right | Check for 1 |
| Check for 1 | 1 | 1 | Right | Find the end |
| Check for 1 | □ | □ | Stay | Halt |
| Find the end | 0 | 0 | Right | Find the end |
| Find the end | 1 | 1 | Right | Find the end |
| Find the end | □ | □ | Left | Borrow |
| Borrow | 0 | 1 | Left | Borrow |
| Borrow | 1 | 0 | Stay | Halt |
The outlined rule is the one the machine will use next.