MTM · Recursively enumerable
aⁿbⁿcⁿ in one pass, with two tapes
The second tape is a ruler. Each a draws a mark on it; each b steps the ruler’s head back over one mark; each c steps it forward again. One left-to-right sweep, so linear time — where a single tape must zigzag and takes time proportional to n².
The author’s examples, run
ε → acceptabc → acceptaabbcc → acceptaaaabbbbcccc → accepta → rejectbbc → rejectbabbcc → rejectbaaabbbbcccc → reject