| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Theory of One Tape Linear Time Turing Machines | Kohtaro Tadaki
; Tomoyuki Yamakami
; Jack C.H. Lin
; | Date: |
23 Oct 2003 | Subject: | Computational Complexity ACM-class: F.1.1; F.1.2; F.4.3 | cs.CC | Abstract: | A theory of one-tape linear-time Turing machines is quite different from its polynomial-time counterpart since one-tape linear-time Turing 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 height of its computation tree. We clarify how the machine types affect the computational patterns of one-tape linear-time Turing machines. | Source: | arXiv, cs.CC/0310046 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |