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.

Two of my last questions seem to have been quickly dispatched; one completely, and the other mostly (I have edited it to make it more viable). In either event, I actually had one other question I meant to ask, and would be interested to lay this subject to rest for good and all. So here it is:

A two-stack PDA can simulate a Turing machine. A k-heap nondeterministic type-1 min-heap automaton cannot (it seems; see the linked question). What about a k-tape nondeterministic type-1 min-heap automaton augmented with a stack (similar to that of a PDA)? Can it simulate a Turing machine? If not, does an augmented (k+1)-heap nondeterministic type-1 min-heap automaton accept a class of languages which is a proper superset of languages accepted by augmented automata with only k heaps?

Thanks, and I promise this is the last of these questions.

Explanation / Answer

A heap and a stack can both be used to implement a counter. 2 counters suffice to recognize RE.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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