SOME RESULTS ON TAPE-BOUNDED TURING MACHINES

被引：50

作者：

HOPCROFT, JE

ULLMAN, JD

机构：

[1] Cornell University, New York and Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

[2] Bell Telephone Laboratories, Inc., Murray Hill, New Jersey

来源：

JOURNAL OF THE ACM | 1969年 / 16卷 / 01期

关键词：

D O I：

10.1145/321495.321508

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Classes of tape-bounded Turing machines similar to the on-line and off-line Turing machines, but without the restrictions that each machine halt and be deterministic, are studied. It is shown that the lower bounds on tape complexity of [1] depend on neither the halting assumption nor determinism. The existence of a dense hierarchy of complexity classes likewise does not depend on the halting assumption, and it is shown that below log n tape complexity there exists a dense hierarchy of complexity classes for two-way nondeterministic devices. It is also shown that the complexity classes of one-way, nondeterministic machines below linear large complexity are not closed under complementation and are larger that the corresponding deterministic complexity class. © 1969, ACM. All rights reserved.

引用

页码：168 / &