MTM · Recursively enumerable
Palindromes in linear time
Copy, rewind, compare: tape 1 read forwards against tape 2 read backwards. The construction a second tape exists for — Θ(n) here against Θ(n²) for the same language on one tape.
The author’s examples, run
abba,ε → acceptaba,ε → acceptabab,ε → rejecta,ε → acceptε,ε → accept