### Two-Tape Simulation of Multitape Turing MachinesTwo-Tape Simulation of Multitape Turing Machines

Access Restriction
Subscribed

 Author Hennie, F. C. ♦ Stearns, R. E. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1966 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{T}$ for a $\textit{k}-tape$ realization, then it requires at most computation time $\textit{T}$ log $\textit{T}$ for a two-tape realization. The proof of this fact is constructive; given any $\textit{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 $\textit{T}(\textit{n})$ and $\textit{U}(\textit{n})$ are two time functions such that inf $\textit{T}(\textit{n})$ log $\textit{T}(\textit{n})$ ÷ $\textit{U}(\textit{n})$ = 0 then there exists a function that can be computed within the time bound $\textit{U}(\textit{n})$ but not within the time bound $\textit{T}(\textit{n}).$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1966-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 13 Issue Number 4 Page Count 14 Starting Page 533 Ending Page 546

#### Open content in new tab

Source: ACM Digital Library