1. A 2-PDA is a push-down automaton with two stacks instead of one. Prove that a 2-PDA is equivalent to a Turing Machine. Note that you will need to prove both of the following:

a. A 2-PDA can simulate a Turing Machine. (HINT: To get started, call the stacks the left stack and the right stack. To set up the simulation, begin by pushing _ onto the left and right stacks. Then, push every character in the input string onto the left stack. Then, pop every character from the left stack and push it onto the right stack. Below is partial transition diagram showing this set-up, where the input alphabet ? = {0,1} and ? = {0,1,_} where _ is the blank character and q_TM-start is the start state for the Turing Machine simulation. You do not need to sketch a diagram for the simulation. Just describe the action of the 2-PDA based on the Turing Machines transition function ?: Q X ? ? Q X ? X {L,R}. Note that all of the transitions in the simulation will be ?-transitions, since the input was completely processed by the setup.)

b. A Turing Machine can simulate a 2-PDA. (HINT: Use a multi-tape non-deterministic Turing Machine.)

Ft R: ? gright-setup qstart qleft-setup QrM-start L: 1 ? Ft R: ? gright-setup qstart qleft-setup QrM-start L: 1