MTM · Recursively enumerable
Balanced parentheses, with a second tape for a stack
A Turing machine has no stack, but a second tape is one: write a mark and step right for each (, step left and erase for each ). One pass, against the one-tape machine’s walking back and forth to find each partner.
The author’s examples, run
ε → accept(()) → accept(()()) → accept(()())(()()) → accept( → reject)()) → reject)()()) → reject)()())(()()) → reject