Two heads are better than two tapes
<|reference_start|>Two heads are better than two tapes: 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 with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape. In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes.<|reference_end|>
@article{jiang2001two,
    title={Two heads are better than two tapes},
    author={Tao Jiang (McMaster University), Joel Seiferas (Rochester University),
  and Paul Vitanyi (CWI and University of Amsterdam)},
    journal={T. Jiang, J. Seiferas and P.M.B. Vitanyi, Two heads are better
  than two tapes, J. Assoc. Comp. Mach., 44:2(1997), 237--256},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0110039},
    primaryClass={cs.CC}
}