Library

LBA · Context-sensitive

Powers of two, by halving

@thethinkmachine·version 1·CC BY 4.0·added 28 Sept 2026

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.

Open in AutomataStudio
More
Open in the desktop app Download the .automaton file Source on GitHub
passsaw oneevenodd ≥ 3rewindacc
The machine as drawn — 6 states, 14 transitions.

The author’s examples, run

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