Library

ITM · Recursively enumerable

Binary increment

Run to the right end of the number, then add 1 the way it is done by hand: 1s turn to 0s while the carry moves left, and the first 0 — or the blank beyond the number — becomes a 1. On a two-way tape the number can grow to the left, so 111 becomes 1000 without moving anything.

rightcarrydone0 → 0, R1 → 1, R⊔ → ⊔, L1 → 0, L0 → 1, S⊔ → 1, S
The machine as drawn — 3 states, 6 transitions.

The author’s examples, run

ε → accept00110 → accept0 → accept000000110 → accept

Behaviour

The first steps from a blank tape: one row per step, time running down; the outlined cell is the head.

Halts from a blank tape after 2 steps, leaving 1 non-blank cells.