Two heads are better than two tapes
| dc.creator | Jiang, Tao | |
| dc.creator | Seiferas, Joel | |
| dc.creator | Vitanyi, Paul | |
| dc.date | 2001-10-18 | |
| dc.date.accessioned | 2026-07-07T03:17:49Z | |
| dc.date.available | 2026-07-07T03:17:49Z | |
| dc.description | 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. | |
| dc.description | LaTeX, 16 pages. The final journal paper contains minor corrections as well as some extra typos, but, also, some clarifying figures. A close copy to that can be downloaded from http://www.cwi.nl/~paulv/complexity.html | |
| dc.identifier | https://arxiv.org/abs/cs/0110039 | |
| dc.identifier | http://arxiv.org/abs/cs/0110039 | |
| dc.identifier | 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 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30865 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2, F.1.1 | |
| dc.title | Two heads are better than two tapes | |
| dc.type | text |