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.
The author’s examples, run
ε → accept00110 → accept0 → accept0001100 → accept
Behaviour
Halts from a blank tape after 2 steps, leaving 0 non-blank cells.