Library

LBA · Context-sensitive

Powers of two, by halving

Accepts aⁿ iff n = 2ᵏ. Each pass crosses off every second a, halving the count; a clean halving chain down to 1 is only possible for powers of two.

passsaw oneevenodd ≥ 3rewindacc⊢ → ⊢, RX → X, Ra → a, RX → X, Ra → X, R⊣ → ⊣, SX → X, Ra → a, R⊣ → ⊣, LX → X, Ra → X, RX → X, La → a, L⊢ → ⊢, R
The machine as drawn — 6 states, 14 transitions.

The author’s examples, run

a → acceptaaaa → acceptaaaaaaaa → acceptaaaaaaaaaaaaaaaa → acceptaaaaaa → rejectaaaaa → reject