Library

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.

q1q2accq3q4q50 → ⊔, Rx → x, R⊔ → ⊔, R0 → x, Rx → x, R0 → 0, R⊔ → ⊔, Lx → x, R0 → x, R0 → 0, Lx → x, L⊔ → ⊔, R
The machine as drawn — 6 states, 12 transitions.

The author’s examples, run

0 → accept00 → accept0000 → accept00000000 → acceptε → reject000 → reject00000 → reject0000000 → reject

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 1 steps, leaving 0 non-blank cells.