Two heads are better than two tapes

ABSTRACT

We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.

REFERENCES

• 1: AANDERAA, S. 0. 1974. 1974. On k-tape versus (k - 1)-tape real time computation. In Complexity of Computation (SIAM-AMS Proceedings 7) R. M. Karp. ed. American Mathematical Society, Providence, R. I., pp. 75-96.
• 2: BE#V#.#,, J. 1965. Real-time and complexity problems in automata theory. Kyberntika 1, 6, 475- 497.
• 3: Victor L. Bennison, Saving tapes in the simulation of multihead turing machines, ACM SIGACT News, v.6 n.2, p.23-26, April 1974 [doi>10.1145/1008304.1008308]
• 4: CHUNG, F. R. K., TARJAN, R. E., PAUL, W. J., AND REISCHUK, R. 1985. Coding strings by pairs of strings. SIAM J. Disc. Math. 6, 3 (July), 445-461.
• 5: Pavol Dūris , Zvi Galil , Wolfgang Paul , Ruediger Reischuk, Two nonlinear lower bounds for on-line computations, Information and Control, v.60 n.1-3, p.1-11, Jan./Feb./Mar. 1984 [doi>10.1016/S0019-9958(84)80019-4]
• 6: Patrick C. Fischer , Albert R. Meyer , Arnold L. Rosenberg, Real-Time Simulation of Multihead Tape Units, Journal of the ACM (JACM), v.19 n.4, p.590-607, Oct. 1972 [doi>10.1145/321724.321726]
• 7: GRIGORmV, D. Yu. 1977. Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms. Soy. Math. 18, 3 (May-June), 588-592.
• 8: HARTMANIS, J., AND STEARNS, R.E. 1965. On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 5 (May), 285-306.
• 9: HENNIE, F.C. 1966. On-line Turing machine computations. IEEE Trans. Elect. Comput. EC-15, 1 (Feb.), 35-44.
• 10: KOLMOGOROV, A.N. 1965. Three approaches to the quantitative definition of information. Prob. Inf. Transm. 1, 1 (Jan.-Mar.), 1-7.
• 11: Benton L. Leong , Joel I. Seiferas, New Real-Time Simulations of Multihead Tape Units, Journal of the ACM (JACM), v.28 n.1, p.166-180, Jan. 1981 [doi>10.1145/322234.322246]
• 12: Ming Li , Luc Longpré , Paul Vitányi, The power of the queue, SIAM Journal on Computing, v.21 n.4, p.697-712, Aug. 1992 [doi>10.1137/0221042]
• 13: Ming Li , Paul M. B. Vitanyi, Tape versus queue and stacks: the lower bounds, Information and Computation, v.78 n.1, p.56-85, July 1988 [doi>10.1016/0890-5401(88)90003-X]
• 14: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993
• 15: MAASS, W. 1985. Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. Trans. Am. Math. Soc. 292, 2 (Dec.), 675-693.
• 16: Wolfgang Maass , George Schnitger , Endre Szemerédi , György Turán, Two tapes versus one for off-line Turing machines, Computational Complexity, v.3 n.4, p.392-401, Oct. 1993 [doi>10.1007/BF01275490]
• 17: MEYER, A.R. 1971. An optimal time bound for a one tape on-line Turing machine computation. Unpublished manuscript. (Earlier version cited in MEYER EY AL. 1967.)
• 18: MEYER, A. R., ROSENBERG, A. L., AND FISCHER, P. C. 1967. Turing machines with several read-write heads, preliminary report. In IEEE Conference Record of 1967 8th Annual Symposium on Switching and Automata Theory. IEEE Computer Society, Long Beach, Calif., pp. 117-127.
• 19: Ramamohan Paturi , Joel I. Seiferas , Janos Simon , Richard E. Newman-Wolfe, Milking the Aanderaa argument, Information and Computation, v.88 n.1, p.88-104, Sep. 1990 [doi>10.1016/0890-5401(90)90005-3]
• 20: PAUL, W.J. 1982. On-line simulation of k + 1 tapes by k tapes requires nonlinear time. Inf. Cont. 53, 1-2 (Apr.-May), 1-8.
• 21: PAUL, W.J. 1984. On heads versus tapes. Theoret. Comput. Sci. 28, 1-2 (Jan.), 1-12.
• 22: PAUL, W. J., SEIFERAS, J. I., AND SIMON, J. 1981. An information-theoretic approach to time bounds for on-line computation. J. Comput. Syst. Sci. 23, 2 (Oct.), 108-126.
• 23: RABIN, M.O. 1963. Real time computation. Is. J. Math. 1, 4 (Dec.), 203-211.
• 24: W. Schnitzlein , H.-J. Stoss, Linear-time simulation of multihead turing machines, Information and Computation, v.81 n.3, p.353-363, June 1989 [doi>10.1016/0890-5401(89)90037-0]
• 25: STOI3, H.-J. 1970. k-Band-Simulation von k-Kopf-Turing-Maschinen. Computing 6, 3, 309-317 (in German).
• 26: VALmV, K. 1970/1973. Certain estimates of the time of computation on Turing machines with an input. Cybernetics 6, 6 (June 1973), 734-741 (translated from Russian, published in Kibernetika 6, 6 (Nov.-Dec. 1970), 26-32).
• 27: VITANYI, P. M.B. 1984. On two-tape real-time computation and queues. J. Comput. Syst. Sci. 29, 3 (Dec.), 303-311.
• 28: ZVONKIN, A. K., AND LEVIN, g.A. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25, 6 (Nov.-Dec.), 83-124.

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Theory