Two heads are better than two tapes
Tao Jiang, Joel Seiferas, Paul M. B. Vitanyi · 1994
. We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set f x2x 0 j x 2 f0; 1g and x 0 is a prefix of x g 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. 1. Introduction The Turing machines commonly used and studied in computer science have separate tapes for input/output and for storage, so that we can conveniently study both storage as a dynamic resource and the more complex storage structures required for efficient implementation of practical algorithms [HS65]. Early researchers [MRF67] asked specifically whether two-head storage is more powerful if both heads are on the same one-dimensional storage tape than if t...