Library

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.

c0copyrewcmpaccbackstep
The machine as drawn — 7 states, 20 transitions.

The author’s examples, run

ab#aab → acceptb#aaab → accept#ab → acceptaba#babab → acceptab#bba → rejectbb#abab → rejectab → reject