F. C. Hennie
R. E. Stearns
Abstract
It has long been known that increasing the number of tapes used by a Turing machine does not provide the ability to compute any new functions. On the other hand, the use of extra tapes does make it possible to speed up the computation of certain functions. It is known that a square factor is sometimes required for a one-tape machine to behave as a two-tape machine and that a square factor is always sufficient.
The purpose of this paper is to show that, if a given function requires computation time T for a k-tape realization, then it requires at most computation time T log T for a two-tape realization. The proof of this fact is constructive; given any k-tape machine, it is shown how to design an equivalent two-tape machine that operates within the stated time bounds. In addition to being interesting in its own right, the trade-off relation between number of tapes and speed of computation can be used in a diagonalization argument to show that if T(n) and U(n) are two time functions such that inf T(n) log T(n) ÷ U(n) = 0 then there exists a function that can be computed within the time bound U(n) but not within the time bound T(n).
- 1 TURINO, A. IVL On computable numbers, with an application to the Entscheidungsproblem Proc. London Math. Soc. {2}, 42 (1938-37), 230-265; Correction, ibid., 43 (1937), 544-546.Google Scholar
- 2 HARTMANIS, J., AND STEARNS, R. E. 0II. the computational complexity of algorithms. Trans. Amer. Math. Soc. 117 (May 1965), 285-306.Google Scholar
- 3 HENNIE, F. C. One-tape, off-line Turing machine computations. Inform. and Contr. 8, 6 (Dec. 1965), 553-578.Google Scholar
- 4 YAMADA, H. Real-time computation and recursivc functions not real-time computable. IRE Trans. EC-11 (1962), 753-760.Google Scholar
Index Terms
- Two-Tape Simulation of Multitape Turing Machines
Recommendations
Time- and tape-bounded Turing machines
Formal languages and their relation to automataFrom the Preface (See Front Matter for full Preface)
The study of formal languages constitutes an important subarea of computer science. This area sprang to life around 1956 when Noam Chomsky gave a mathematical model of a grammar in connection with his ...
The complexity of theorem-proving procedures
STOC '71: Proceedings of the third annual ACM symposium on Theory of computingIt is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology. Here “reduced” means, roughly speaking, ...
Comments