Build a 2-PDA for language accepted by Turing Machine

Question

I saw this question on the internet and found many solutions actually but none of them really persuade me that much.

Question: Given language $L$ which is accepted by a Turing machine $M$, provide a 2-PDA that describes $L$. End of the question.

Note: A Turing machine is given by $M=\{Q,\Sigma,\Gamma,\delta,q_0,q_{accept},q_{reject}\}$.

I assume that the transitions in a 2-PDA look like this:

$$\sigma, \begin{pmatrix} \gamma_1\rightarrow\gamma_2 \\ \gamma_2\rightarrow\gamma_3 \end{pmatrix}$$

Meaning when we see a letter $\sigma$ we remove $\gamma_1$ from the first stack, insert $\gamma_2$ to it, and remove $\gamma_2$ from the second stack and insert $\gamma_3$ to it.

I think there is a simple answer that for a transition $(\sigma_1\rightarrow\sigma_2,L/R)$ in $M$ we can replace it with a transition of the form of a 2-PDA transition but I don't really recognize what is the desired transition.

Answer 1

If the non-blank region of the Turing tape looks like $$ \begin{bmatrix}a_1&a_2& \ldots& a_n& \check{x} &b_1&\ldots& b_m\end{bmatrix}$$ where $\check{x}$ denotes the current position, then the two stacks should look roughly like

$$\begin{bmatrix}a_n\\a_{n-1}\\a_{n-2}\\\vdots \\ a_1\end{bmatrix} \begin{bmatrix}x\\b_1\\b_{2}\\\vdots \\ b_n\end{bmatrix}$$

When the tape head moves left, pop from the left stack and push the same symbol onto the right stack.

When the tape head moves right, pop from the right stack and push the same symbol onto the left stack.

If you move onto blank areas of the tape and run out of symbols to pop in the stack, you are allowed to push a blank symbol so that the stack behaves as if it has an inexhaustible supply of blank symbols. Equivalently, every stack can start with the symbol $\square_\infty$ at the bottom (infinite tape here), and if you would pop it off the stack and push it onto the other stack, you instead leave it where it is and push a single blank symbol $\square$ onto the other stack.