| | |
| | |
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.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |