J. Hartmanis
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.
- 1 HENNIE, F. C. One-tape, off-line Turing machine computations. Inf. Contr. 8 (1965), 553-578.Google Scholar
- 2 HARTMANIS, J., AND STEARINS, R, E. On tile eomttltalimal complexity of algorithms. Trans. Amer. Math. Soc. 117 (May 1965), 285-301.Google Scholar
- 3 STEARNS, R E., HARTMANIS, J., AND LEWIS, P.M. Hierarchies of memory limited computations, iEEE Confereace Ilecord on Switching CircUit Theory and Logical Design, IEEE Pub. 1613, 1965, pp. 179-190.Google Scholar
- 4 TRACTENBROT, B.A. Turing computations with logarithnlie delay. (In Russian.) Algebra i Logica 3 (1964), 33 48. English translalion in U. of California Computing Center, Teeh. llep. No. 5, Berkeley, Calif., 1966.Google Scholar
- 5 RABIN, M. 0., AND SCOTT, D. Finite automata and their decision problems. In Moore, E. F. (ed.), Seqvential Machines: Selected Papers. Addison-Wesley, Reating, Mass., 1964, pp. 63-91.Google Scholar
- 6 HENNIE, F. C., AND STEARNS, R. E. Two-tape simulation of multilape Turing machines. J. ACM 13, 4 (Oct. 1966), 533-546. Google Scholar
- 7 LEWIS, P. M., STEARNS, R. E., AND HARTMANIS, J. Memory bolmds for recognition of con{ext-free and context-serYsitive languages. IEEE Conference llecord on Switching Circuit Theory and Logical Design, IEEE Pub. 16C13, 1965, pit. 191 202.Google Scholar
- 8 YOUNGER, D. H. Context-free language processing in time n2 . Proc. 1966 Seventh Auroral Symposium on Switching and Automata Theory. IEEE, New York, 1966, pp. 7-20.Google Scholar
- 9 POST, E. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), 262-268.Google Scholar
- 10 GINSBURG, S. The Mathematical Theory of Context-Free Languages. McGraw-Hill, New York, 1966. Google Scholar
Index Terms
- Computational Complexity of One-Tape Turing Machine Computations
Recommendations
Theory of one-tape linear-time Turing machines
A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues ...
Nondeterministic one-tape off-line turing machines and their time complexity
In this paper we consider the time and the crossing sequence complexities of one-tape off-line Turing machines. We show that the running time of each nondeterministic machine accepting a nonregular language must grow at least as n log n, in the case all ...
Weak synchronization and synchronizability of multi-tape pushdown automata and turing machines
Given an n-tape automaton M with a one-way read-only head per tape which is delimited by an end marker $ and a nonnegative integer k, we say that M is weakly k-synchronized if for every n-tuple x = (x1,..., xn) that is accepted, there is an accepting ...
Comments