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
      0 references
      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
      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

      Identifiers