Computational power of a 2-PDA In our CS class, we have a question about the computational power of PDA's (Push Down Automaton).  A 0-PDA (PDA with no stacks) is equivalent to an NFA (Non-deteministic Finite Automaton), while a 1-PDA (the standard PDA) is equivalent to a CFG (Context Free Grammar).

However, a 2-PDA (PDA with 2 stacks) is more powerful (recognises more languages) than a 1-PDA, because it is not limited to pushing and popping on 1 stack only, but can also use the second stack.

The problem that I have is that I don't know how to prove the greater power of the 2-PDA.  My first thought was that a 2-PDA would be equivalent to a Turing Machine, but then I realised that it still wouldn't quite provide arbitrary access to the stack.

How would I go about proving that a 2-PDA is more powerful than a 1-PDA?

(Could someone with enough rep please tag this as homeworkpda - thanks)
First: Student's heuristics. At your level, what can you prove? Equivalence with TM or PDA should work by simulation. Equivalence to LBA might be slightly harder. Anything in between is certainly harder. So start with the easy inclusions.

You can see very quickly that languages like $a^nb^nc^n$ that are not context-free can be accepted by a 2-PDA. So you are certainly stronger than PDA.

Next in line is TM. Of course, every 2-PDA can be simulated by a 2-TM which can in turn be simulated by a TM. Turns out that the other direction works out, too. Take a TM and simulate it by a 2-PDA. You can keep the state graph but have to translate reading/writing/moving to reading$^2$/writing$^2$. What can simulate the TM's head? Also, take care what happens if the TM accesses new fields.

Can you figure it out now?