Theory of one-tape linear-time Turing machines |
| |
Authors: | Kohtaro Tadaki Tomoyuki Yamakami Jack CH Lin |
| |
Affiliation: | a ERATO Quantum Computation and Information Project, Japan Science and Technology Corporation, Tokyo, 113-0033, Japan b School of Information Technology and Engineering, University of Ottawa, Ottawa, Ontario, Canada, K1N 6N5 |
| |
Abstract: | 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 of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines’ resources affect their computational patterns and power. |
| |
Keywords: | One-tape Turing machine Crossing sequence Finite state automaton Regular language One-way function Low set Advice Many-one reducibility |
本文献已被 ScienceDirect 等数据库收录! |
|