Computational Complexity of One-Tape Turing Machine Computations
- 1 April 1968
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 15 (2) , 325-339
- https://doi.org/10.1145/321450.321464
Abstract
The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of nonregular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences, and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a nonregular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.Keywords
This publication has 4 references indexed in Scilit:
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966
- One-tape, off-line Turing machine computationsInformation and Control, 1965
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946