I have asked a series of questions concerning capabilities of a certain class of

Question

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

This question concerns the power of type-1 min-heap automata, which represent my initial idea for how these machines would operate. The class of languages which can be accepted by such automata is incomparable (i.e., neither a proper subset nor a proper superset) of the set of context-free languages.

Push down automata, which possess a single stack for data storage, accept the set of context-free languages, in the same way that min-heap automata, which possess a single heap for data storage, accept the set HAL1 of languages accepted by nondeterministic type-1 min-heap automata. Push-down automata with two stacks are equivalent to Turing machines in computational power; they can simulate Turing machines, and vice versa; which leads me to my question:

Does adding another heap to non-deterministic type-1 min-heap automata make them equivalent in terms of computing ability to Turing machines, in the sense that they are able to simulate Turing machines? If not, does it increase their computational power at all, in the sense that nondeterministic type-1 min-heap automata can accept a set of languages which is a proper subset of HAL1? If so, does adding additional heaps increase computational power, i.e., can nondeterministic min-heap automata with k+1 heaps accept more languages than automata with k heaps, for any k?

This is one of the last questions I plan to ask about these automata; if good answers can be had for these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.

Explanation / Answer

Although the first answer has already been accepted, I understand that the power of the multiple heap automata described here have not been resolved.

With two heaps, and just a single heap symbol each (apart from the bottom-of-heap), it seems one can simulate a two-counter automaton. Such an automaton keeps two natural numbers, that can be incremented, decremented, and tested for zero. You can push and pop, and also test for bottom-of-stack, which is equivalent for zero test. Only two of these are sufficient to simulate a Turing Machine! The proof of this fact is in the first edition of the Hopcroft Ulmann book, Theorem 7.9, but seems originally from Minsky (1961). The many-counter automaton (with zero tests) is equivalent to the notion of register machine.

Thus, if I understand your definition well, the two min-heap version of your HAL models are equivalent to RE.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.