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:

  1. 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
  2. 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
  3. Otherwise, replace that letter with \Delta and head the tape head to the left, to prevent hitting the \# marker
  4. 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:

  1. 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
  2. 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.


乱我心者,今日之日多烦忧