Question

You may recall in last week's extra credit, we showed that if you give a PDA 2 stacks instead of 1, it's able to accept the language a^n b^n c^n that no normal PDA could accept. This week, we'll show an even stronger result Show how any Turing machine can be converted to an equivalent 2-stack PDA. (This proves that the set of languages 2-stack PDAs can be built to accept is exactly the set of decidable languages)

Answer 1

Solution:

To convert the turning machine into 2 stack PDA we need our turning machine to be infinite in only one side of the tape, contents of the tape to
the left of the current position and the second stack as the contents to the right. We can start by pushing the elements in Bottom of the stack
markers like an element Z then we can use these two stack for the direction of Turing Machine, we can simulate the TM by popping from the left stack
and pushing to the right to move left, and vice versa to move right. Now in the process if bottom of the left stack is met then we can halt and reject,
but if we hit the bottom of the right stack first we can push a blank symbol onto the left stack.

Basically all we need to do is pop to read and push to write.