Minsky's Theorem

A two-pushdown stack machine, abbr. 2PDA, is a PDA with two pushdown stacks, the $\tt PUSH$ and $\tt POP$ operations must specify which stack they operate on, and 2PDA is deterministic.

2PDAs can actually accept some non-context-free langauges, for example, the following 2PDA acceptes old friend $a^nb^na^n$ , it can be achieved by putting the three clusters of $a$ and $b$ into two stacks alternately

Turing equivalency

2PDA=TM

Proof

Let $P$ be a 2PDA, The core idea of this proof is to flatten the three storage of $P$ into a single storage, which is the tape of the TM, at first, we put all the contents on the input tape of $P$ to the tape of TM $T$ , then insert a $\Delta$ at the very beginning of the tape of $T$ , every time $P$ reads a letter, we replace the corresponding letter to $\Delta$ on the $T$ 's tape to simulates a consumption. We'll put a $\#$ at the end of the content on $T$ 's tape, which is the end of the input string, it'll be considered as a base pointer, no matter how the tape head moves, it must return to the $\#$ after finitely many steps before begin its next operation.
For a $\tt READ$ operation on the $P$ with three outgoing edges lead to states $X$ , $Y$ and $Z$ each of which labeled with $a$ , $b$ and $\Delta$ respectively, we do the following operations on the $T$ to simulate it:

Find the first non- $\Delta$ character on the tape, since we've inserted a $\Delta$ before machine starts this would be easy by using the algorithm we've frequently employed
If the first non- $\Delta$ character is $\#$ , then the input string has been exhausted, we go to state $Z$ because the state $Z$ stands for a $\Delta$ edge
Otherwise, replace that letter with $\Delta$ and head the tape head to the left, to prevent hitting the $\#$ marker
Go to the proper state decided by the character we've just read, then reset the tape head back to $\#$

The two stacks' content will appears from the left to right separated by $\text{\textdollar}$ after the $\#$ , for a $\tt POP_1$ state with three edges lead to $X$ , $Y$ and $Z$ each of which labeled with $a$ , $b$ and $\Delta$ respectively, we do the following to simulate it:

Move the tape head to the right, if we meet $\text{\textdollar}$ then the $\tt STACK_1$ must be empty, we write $\text{\textdollar}$ and head the tape head to left, then we go to state $Z$ since it's marked with $\Delta$ and reset the tape head
Otherwise we go to the proper state that decided by the character we read, then delete the character we read and reset the tape head( $\tt DELETE$ is a subprogram can be implemented by TM)

To simulate a $\tt PUSH_1\text{ x}$ state, just call the $\tt INSERT\text{ x}$ and then reset the tape head

The $\tt PUSH_2$ and $\tt POP_2$ is very similar, just move the tape head to $\text{\textdollar}$ then do exactly the same thing as to the $\tt PUSH_1$ and $\tt POP_1$
When the $P$ reaches an $\tt ACCEPT$ , we $\tt HALT$ the TM $T$
To show the second part, which is that prove every langauge accepted by a TM can be accepted by some 2PDA, we do a simple exchange, let's prove that every langauge accepted by a PM can be accepted by some 2PDA, since we've proved that PM=TM, so this could also prove that 2PDA=TM. Firstly, we transfer all the contents on the input tape of $P$ to its $\tt STACK_1$ while maintaining the same order, we can do this by put them in $\tt STACK_2$ first, which will reverse the order of input string, then pop them from $\tt STACK_2$ and pushes back to $\tt STACK_1$ , now we need to simulate two operations of the PM, $\tt ADD$ and $\tt READ$ , the $\tt READ$ operation is same as the $\tt POP_1$ operation on $P$ since both of them remove the character at the very beginning at the input string then branching accordingly, the $\tt ADD\text{ x}$ state, on the other hand, is a bit tricky, we need to empty $\tt STACK_1$ to $\tt STACK_2$ first, the push $x$ to the $\tt STACK_1$ , then we pop all the contents in $\tt STACK_2$ and push the back to the $\tt STACK_1$ , this make the $x$ becomes the bottommost element which is just like the rightmost element on the $\tt STORE$ of the PM, while keep the order of other characters in the $\tt STACK_1$ , since the PMs contain only these two operations, we can consider we've successfully simulated a 2PDA on PM, from the first and second part of this proof, we have 2PDA=TM
ocean liner.

n-Stack PDA

A PDA with $n$ -Stacks is equivalent with 2PDA, in other words, nPDA=TM

Proof

There will be no even more powerful machines can be constructed by simply adding more stacks, the proof is very simple, for PDA with $n$ stack, we separate the tape of the TM into $n+2$ sections, where the first section is the contents on the input tape of nPDA, the following $n+1$ sections represent the $n$ stacks of the nPDA, and then the last section is filled with blanks, it is obvious that we can build such a machine by repeating the algorithm in the previous proof.