New real-time simulations of multihead tape units

ABSTRACT

Just as the Church-Turing thesis has simplified proofs of computability [8], efficient simulations of one computer model by another have simplified proofs of complexity upper bounds. A good example of this is Fischer, Meyer, and Rosenberg's real-time simulation of multihead Turing machines by multitape Turing machines [5]. Without this result, for example, even Slisenko [11] may have found it hopeless to show that a multitape Turing machine can recognize palindromes in real time. In this paper we give a comparatively simple proof of the Fischer-Meyer-Rosenberg result, dramatically reduce the number of single-head tapes required for the simulation, and generalize the result to multidimensional tapes. In the case of Slisenko's palindrome-recognizer, for example, our best simulation brings the number of tapes for a multitape Turing machine implementation down from 41 to 20.

REFERENCES

• 1: S. O. Aanderaa, On k-tape versus (k-1)-tape real time computation, in Complexity of Computation (SIAM-AMS Proceedings, Vol. 7), R. M. Karp, ed., American Mathematical Society, Providence, Rhode Island, 1974, pp. 75-96.
• 2: 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]
• 3: M. J. Fischer, personal communication.
• 4: M. J Fischer and A. L. Rosenberg, Limited random access machines (preliminary version), IEEE Conference Record of 1968 Ninth Annual Symposium on Switching and Automata Theory, Schenectady, New York, 1968, pp. 356-367.
• 5: 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]
• 6: J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of the American Mathematical Society, Vol. 117, May 1965, pp. 285-306.
• 7: F. C. Hennie, On-line Turing machine computations, IEEE Transactions on Electronic Computers, Vol. EC-15, No. 1, February 1966, pp. 35-44.
• 8: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 9: W. J. Savitch and P. M. B. Vitányi, Almost real time simulation of multihead Turing machines with head-to-head jumps (extended abstract), Mathematisch Centrum, Amsterdam, The Netherlands, 1976.
• 10: J. I. Seiferas, Iterative arrays with direct central control, Acta Informatica, to appear.
• 11: A. O. Slisenko, Recognition of palindromes by multihead Turing machines, in Problems in the Constructive Trend in Mathematics. VI (Proceedings of the Steklov Institute of Mathematics, No. 129), V. P. Orevkov and N. A. Šanin, ed., Academy of Sciences of the USSR, 1973, pp. 30-202; English translation by R. H. Silverman, American Mathematical Society, Providence, Rhode Island, 1976, pp. 25-208.
• 12: R. E. Stearns, J. Hartmanis and P. M. Lewis, II, Hierarchies of memory limited computations, IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Michigan, 1965, pp. 179-190.
• 13: H. J. Stoss, k-Band-Simulation von k-Kopf-Turing-Maschinen, Computing, Vol. 6, Fasc. 3, 1970, pp. 309-317.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Recursive function theory

General Terms:
Performance