Two Tapes are Better than One for Nondeterministic Machines (Q3347301)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3890737
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Two Tapes are Better than One for Nondeterministic Machines |
scientific article; zbMATH DE number 3890737 |
Statements
Two Tapes are Better than One for Nondeterministic Machines (English)
0 references
1984
0 references
computational power of real-time nondeterministic Turing machines
0 references
two working tapes
0 references
single working tape
0 references
reversal-bounded machines
0 references
two pushdown stores
0 references
0.8432027697563171
0 references
0.7953180074691772
0 references
0.7940258383750916
0 references
This paper solves two open questions about the computational power of real-time nondeterministic Turing machines (ndTms) with a different number of working tapes or pushdown stores. A machine is real-time if it reads a new input symbol in every step, and stops immediately after reading the endmarker. The first result states that an ndTm with two working tapes accepts in real time more languages that an ndTm with a single working tape, while it is well known that furtherly increasing the number of tapes does not affect the power of the machine [\textit{R. V. Book} and \textit{S. A. Greibach}, Math. Syst. Theory 4, 97-111 (1970; Zbl 0188.331)]. A second theorem shows that even two pushdown stores are sufficient to increase the computational power of one-tape ndTms. The same questions are then solved in the case of reversal-bounded machines, that is machines whose heads are allowed to make only a constant number of reversals. Even for such machines, it is shown that two tapes are better than one and that two pushdown stores are better than one tape. Finally, it is shown that real-time one-tape ndTm without restrictions are more powerful than the corresponding reversal-bounded machines. The paper terminates with a list of further open problems about the power of linear-time ndTm and their comparison with real-time machines: Are linear-time one-tape ndTms better than real-time one-tape machines? Are linear-time two-tape ndTms better than linear-time one-tape machines? Are linear-time two-pushdown ndTms better than linear-time one-tape machines? Are linear-time three-pushdown ndTms better than linear-time two-pushdown machines?
0 references