Question

Please Provide Detailed Answer. Prove that a PDA that has access to two stacks is as powerful as a Turing Machine. Such a PDA has labels on the transition arrows of the form (a, α, β → α' , β' ), meaning that read an a from the input, pop an α from the first stack, β from the second stack, and push α' on the first stack, and β' on the second stack.

Answer 1

Turing Machine is a powerful computing model that can simulate any computer program.Turing Machine is a powerful computing model that can simulate any computer program.

A Turing machine can accept languages not accepted by any PDA with one stack.

The strength of pushdown automata can be increased by adding additional stacks.

Actually, a PDA with two stacks has the same computation power as a Turing Machine.

Two-Stack PDA is a computational model based on the generalization of Pushdown Automata (PDA).

Non-deterministic Two-Stack PDA is equivalent to a deterministic Two-Stack PDA.

The move of the Two-Stack PDA is based on

−The state of the finite control.

−The input symbol read.

−The top stack symbol on each of its stacks.

Tt is easy to see that Turing machines are at least as powerful as two stack machines since for every two stack machine you can construct a Turing machine that emulates the first stack with the half of the tape that is to the left of the read/write head, and the other stack with the square under the head plus the right half of the tape. A push or pop operation on either stack can be emulated in the Turing machine by moving all the symbols on the appropriate half of the tape either one square to the left or right. The time it takes to do that on the Turing machine is proportional to the height of the stack, whereas it takes only 1 step on the two stack machine, but the timing contrast is irrelevant.

Likewise, the class of two stack machines is equally powerful as the class of Turing machines. The trick is similar. We represent the left half of the Turing machine tape with the first stack, and the square under the read head plus the right half of the tape with the second stack. Moving the Turing machine head left or right is a matter of popping a symbol off of one stack and pushing it onto the other. Reading the location under the tape head is just a matter of reading the symbol at the top of the second stack. Writing the location under the tape head is emulated by popping one symbol from the top of the second stack and then pushing the new symbol onto it.

That is essentially all there is to the proof