|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article forum
| |
|
|
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 message found in this article forum.
You have a question or message about this article?
Ask the community and write a message in the forum.
If you want to rate this article, please use the review section..
To add a message in the forum, you need to login or register first. (free): registration page
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER