TM · Recursively enumerable
Palindromes on one tape
Erase the first symbol, remember it, run to the far end and erase the last symbol if it matches; repeat from the new first symbol. About n²/2 steps for a word of length n — and no one-tape machine can do fundamentally better, which is what the two-tape palindrome machine is for.
The author’s examples, run
ε → acceptabba → acceptaa → acceptaaabbbaaa → acceptbbba → rejectba → rejectbaabbbaaa → rejectab → reject
Behaviour
Halts from a blank tape after 1 steps, leaving 0 non-blank cells.