Two Tapes are Better than One for Nondeterministic Machines
computational power of real-time nondeterministic Turing machinesreversal-bounded machinessingle working tapetwo pushdown storestwo working tapes
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?
- Theory of one-tape linear-time Turing machines
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Tape versus queue and stacks: The lower bounds
- Alternating real-time computations
- Simulating two pushdown stores by one tape in \(O(n^{1.5}\,\sqrt{\log \,n})\) time
- Two heads are better than two tapes
- Single-tape reset machines
- scientific article; zbMATH DE number 3943032 (Why is no real title available?)
- scientific article; zbMATH DE number 3976379 (Why is no real title available?)
- scientific article; zbMATH DE number 3980489 (Why is no real title available?)
- scientific article; zbMATH DE number 3984575 (Why is no real title available?)
- scientific article; zbMATH DE number 3988711 (Why is no real title available?)
- Uniform simulations of nondeterministic real time multitape Turing machines
- Two heads are better than two tapes
- Pushdown store machines and real-time computation
- On two-tape real-time computation and queues
This page was built for publication: Two Tapes are Better than One for Nondeterministic Machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3347301)