Library

ITM · Recursively enumerable

Counting to n in binary

Input aⁿ; output n in binary. Erase the last a, walk left past the rest to a binary counter growing leftwards from the input, add 1 to it, and walk back. When the a’s are gone, the counter is the answer: unary to binary in O(n²) steps, and the tape ends up exponentially shorter.

toEndtakebackdoneinc0 → 0, R1 → 1, Ra → a, R⊔ → ⊔, La → ⊔, L0 → 0, S1 → 1, S⊔ → 0, Sa → a, L0 → 1, R⊔ → 1, R1 → 0, L1 → 0, L0 → 1, R⊔ → 1, R
The machine as drawn — 5 states, 15 transitions.

The author’s examples, run

ε → acceptaa → accepta → acceptaaaaaaaaaaaaaa → accept

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