Thanks! Anyone know more about the following fascinating theorem? I'm guessing it's Cook's Theorem (I vaguely recollect from Ullman's Automata course), but I don't recall it the way Knuth puts it:
> Steve Cook had proved a very amazing theorem. He said that if you could, if you took a certain kind of computer that's very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer.
The KMP paper is "Fast Pattern Matching In Strings", which cites Cook's "Linear time simulation of deterministic two-way pushdown automata". The former has a neat history section that gives a little more detail than the interview.
> Steve Cook had proved a very amazing theorem. He said that if you could, if you took a certain kind of computer that's very limited in its capability, and if you could write a program for that dumb kind of computer to solve a problem, no matter how slow that program was then there was a fast way to write a program for a real computer.
[92 - The Knuth-Morris-Pratt algorithm]