Theory of One Tape Linear Time Turing Machines
<|reference_start|>Theory of One Tape Linear Time Turing Machines: A theory of one-tape (one-head) 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.<|reference_end|>
@article{tadaki2003theory,
    title={Theory of One Tape Linear Time Turing Machines},
    author={Kohtaro Tadaki, Tomoyuki Yamakami, and Jack C.H. Lin},
    journal={(journal version) Theoretical Computer Science, Vol.411, pp.22-43,
  2010},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0310046},
    primaryClass={cs.CC}
}