Library

ITM · Recursively enumerable

Binary to unary: counting down

Input n in binary; output n ones. Subtract 1 from the binary number, add a mark at the far left, and repeat until the number is all zeros; then erase it and turn the marks into 1s. The output is exponentially longer than the input, and so is the running time — there is no faster way to write it.

scan0scan1zerodecmarkbackconvdone0 → 0, R1 → 1, R⊔ → ⊔, L0 → 0, R1 → 1, R⊔ → ⊔, L0 → 1, L1 → 0, L0 → 0, L1 → 1, Lx → x, L⊔ → x, Rx → x, R0 → 0, S1 → 1, S0 → ⊔, Lx → 1, L⊔ → ⊔, Sx → 1, L⊔ → ⊔, S
The machine as drawn — 8 states, 20 transitions.

The author’s examples, run

ε → accept00110 → accept0 → accept0001100 → 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 0 non-blank cells.