Two heads are better than two tapes

Details Two heads are better than two tapes Two heads are better than two tapes

2001-10-18

arxiv.org/abs/cs/0110039v1

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

Computer Science

Computational Complexity

LaTeX, 16 pages. The final journal paper contains minor corrections as well as some extra typos, but, also, some clarifying fi

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Two heads are better than two tapes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two heads are better than two tapes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two heads are better than two tapes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-283592