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.
The author’s examples, run
ε → acceptaa → accepta → acceptaaaaaaaaaaaaaa → accept
Behaviour
Halts from a blank tape after 2 steps, leaving 1 non-blank cells.