TM · Recursively enumerable
Sipser’s M2: 0s whose number is a power of 2
Each pass crosses off every other 0, halving the count; an odd count above one means the number was not a power of 2. The first 0 is replaced by a blank so the machine can find the left end of its tape again.
The author’s examples, run
0 → accept00 → accept0000 → accept00000000 → acceptε → reject000 → reject00000 → reject0000000 → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.