|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'503'724
Articles rated: 2609
23 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Two heads are better than two tapes | | Tao Jiang
; Joel Seiferas
; Paul Vitanyi
; | | Date: |
18 Oct 2001 | | Journal: | T. Jiang, J. Seiferas and P.M.B. Vitanyi, Two heads are better than two tapes, J. Assoc. Comp. Mach., 44:2(1997), 237--256 | | Subject: | Computational Complexity ACM-class: F.2.2, F.1.1 | cs.CC | | Affiliation: | McMaster University), Joel Seiferas (Rochester University), and Paul Vitanyi (CWI and University of Amsterdam | | Abstract: | We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x’| x in {0,1}^* and x’ is a prefix of x} in real time, although it can do so with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape. In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes. | | Source: | arXiv, cs.CC/0110039 | | 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 Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER