Problem $2.(10$ points$)$ Describe how a $2-$stack machine can simulate any one step of a standard deterministic, one$-$tape Turing machine. Give a high$-$level description, showing how the TM tape is stored on the two stacks, and how the stacks are manipulated as the TM writes onto a cell and moves the tape head.

The remarkable conclusion is that while a PDA with one stack can recognize only context$-$free languages, a $2-$stack machine is as powerful as a TM$,$ and that adding a third stack does not give it any more power!