Is a push-down automaton with two stacks equivalent to a turing machine?

Question Detail: 

In this answer it is mentioned

A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine).

I wanted to know regarding the truth of the bold part above. Is it in fact true or not? What is a good way to reach at an answer to this?

Asked By : Lazer

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2832

Answered By : Luke Mathieson

Two bits to this answer;

Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata).

The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume that we're using the model of TMs that has a tape that's infinite in one direction only (though both directions is not much harder, and equivalent).

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. Start by pushing the normal "bottom of stack" markers on both stacks, then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

The relationship the other way should be even more obvious, i.e. that we can simulate a two-stack PDA with a TM.