Can a PDA with two stacks accept RE Language?

Question

So, I was having a bit of difficulty figuring what exactly is meant by a String on which Turing Machine does not halt. I read somewhere that a Turing Machine is equivalent to a deterministic automata with 2 stacks. But how will a deterministic automata with 2 stacks accept a string that doesn't halt when for any finite string it is determined to halt... Am I missing something??

Answer 1

A PDA with two stacks is equivalent to a Turing machine. To show a TM is at least as powerful as a two-stack PDA, we can use the fact that a TM is exactly as powerful as a two-tape TM. In a two-tape TM, we can restrict usage of the tapes to simulate their being stacks. So, certainly a TM can do whatever a two-stack PDA can do.

To show a PDA with two stacks is at least as powerful as a two-stack TM is a little trickier, but basically the idea is that you can simulate a single tape using the two stacks as follows:

1. Call one stack L and the other R
2. The contents of L represent everything to the left of the tape head (including the current symbol)
3. The contents of R represent everything to the right of the tape head
4. To overwrite the current symbol: pop from L and push to L
5. To move left in the tape: pop from L and push to R
6. To move right in the tape: pop from R and push to L

So, we can move left and right and overwrite symbols. This lets us simulate a tape, which is all a TM can do anyway.