Loading...
Please wait, while we are loading the content...
Two–way simulation of multitape turing machines (1966).
| Content Provider | CiteSeerX |
|---|---|
| Author | Hennie, F. C. Stearns, R. E. |
| Abstract | 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 twotape 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 ~ddition to being interesting in its own right, the tr~de-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 T(n) log T(n) inf 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. |
| File Format | |
| Publisher Date | 1966-01-01 |
| Access Restriction | Open |
| Subject Keyword | Multitape Turing Machine Way Simulation Time Bound Square Factor Extra Tape K-tape Realization Time Function K-tape Machine Certain Function Diagonalization Argument Twotape Machine One-tape Machine Equivalent Two-tape Machine Turing Machine Tr De-off Relation New Function Stated Time Bound Computation Time Computation Time Log Two-tape Realization |
| Content Type | Text |
| Resource Type | Article |
