TM · Recursively enumerable
0ⁿ1ⁿ by crossing off
The Turing machine Hopcroft, Motwani and Ullman build first: change the leftmost 0 to X, walk right to the leftmost 1 and change it to Y, walk back, repeat. When the 0s run out, only Y’s may remain before the blank.
The author’s examples, run
01 → accept0011 → accept000111 → accept00000001111111 → accept11 → reject1011 → reject100111 → reject10000001111111 → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.