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 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 flow the machines' resources affect their computational patterns and power. (C) 2009 Elsevier B.V. All rights reserved.
one-tape turing machine crossing sequence finite state automaton regular language one-way function low set advice many-one reducibility