MTM · Recursively enumerable
Searching for a pattern: p#t
Does p occur in t? Tape 2 gets a copy of p. Then, for each starting point in t, the two heads compare side by side; on a mismatch both walk back together and the text head moves on by one. The naive string-search algorithm, with a second tape as the pattern buffer.
The author’s examples, run
ab#aab → acceptb#aaab → accept#ab → acceptaba#babab → acceptab#bba → rejectbb#abab → rejectab → reject