Computer Science – Computational Complexity
Scientific paper
2003-10-23
(journal version) Theoretical Computer Science, Vol.411, pp.22-43, 2010
Computer Science
Computational Complexity
26 pages, 10pt, letter size. A few corrections. This is a complete version of the paper that appeared in the Proceedings of th
Scientific paper
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.
Lin Jack C. H.
Tadaki Kohtaro
Yamakami Tomoyuki
No associations
LandOfFree
Theory of One Tape Linear Time Turing Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Theory of One Tape Linear Time Turing Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Theory of One Tape Linear Time Turing Machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-342454