Library

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².

q0asaccbscs
The machine as drawn — 5 states, 8 transitions.

The author’s examples, run

ε → acceptabc → acceptaabbcc → acceptaaaabbbbcccc → accepta → rejectbbc → rejectbabbcc → rejectbaaabbbbcccc → reject