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.
The author’s examples, run
ε → accept00110 → accept0 → accept000000110 → accept
Behaviour
Halts from a blank tape after 2 steps, leaving 1 non-blank cells.