Theory of Computation - Turing Machines

Problem 3. 2-PDA expressiveness 1. It is possible to simulate any (single-tape) TM M with a 2PDA AM. Given any configuration of M in textbook's notation (for example "abaqcda"), we will use the left stack to hold the left half of M's configuration including state ("abaq" in the example) and the right stack to hold the state and the rest of M's configuration ("cda" in the example) It is also possible to simulate any 2-PDA with a three-tape TM, where the first tape of MA initially contains the input string and the other two are initially empty. The contents of the first tape never changes, and the other two correspond to A's stacks 2. 3. It is also the case that the class of TMs is more expressive than the class of regular - stack) PDAs Based on the three facts above, what can you conclude about the class of 2PDAs? How does it compare with regular PDAs? How does it compare with Turing Machines? State your answers as formal Theorems and prove them. Problem 3. 2-PDA expressiveness 1. It is possible to simulate any (single-tape) TM M with a 2PDA AM. Given any configuration of M in textbook's notation (for example "abaqcda"), we will use the left stack to hold the left half of M's configuration including state ("abaq" in the example) and the right stack to hold the state and the rest of M's configuration ("cda" in the example) It is also possible to simulate any 2-PDA with a three-tape TM, where the first tape of MA initially contains the input string and the other two are initially empty. The contents of the first tape never changes, and the other two correspond to A's stacks 2. 3. It is also the case that the class of TMs is more expressive than the class of regular - stack) PDAs Based on the three facts above, what can you conclude about the class of 2PDAs? How does it compare with regular PDAs? How does it compare with Turing Machines? State your answers as formal Theorems and prove them