Two heads are better than two tapes

Tao Jiang, Joel Seiferas, Paul Vitanyi

We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so…