TM · Recursively enumerable
Two equal halves: w#w
The first machine in Sipser’s chapter on Turing machines. Cross off the first symbol, remember it in the state, cross off its partner after the #, and come back; repeat until the left half is gone. Everything is checked with nothing but a pencil and a lot of walking.
The author’s examples, run
# → accept01#01 → accept110#110 → accept10011#10011 → accept0 → reject11#01 → reject010#110 → reject00011#10011 → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.