### Some Results on Tape-Bounded Turing MachinesSome Results on Tape-Bounded Turing Machines

Access Restriction
Subscribed

 Author Hopcroft, J. E. ♦ Ullman, J. D. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1969 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract 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 $\textit{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. 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 1969-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 16 Issue Number 1 Page Count 10 Starting Page 168 Ending Page 177

#### Open content in new tab

Source: ACM Digital Library