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.


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

  • $\begingroup$ Ah, I see that the first stack carries the symbols at the left of the current position and the second carries the symbols at the right. But I don't get why to insert $\square_\infty$ at the beginning of the stacks. $\endgroup$
    – Mohamad S.
    May 6, 2022 at 12:08
  • $\begingroup$ @CSStudent A Turing tape is infinite, even if the stacks are finite. Using the symbol $\square_\infty$ on the stack is one way to represent when the head of the Turing tape has moved from the finite region it's traveled on before, into the infinite blank region. $\endgroup$
    – user326210
    May 7, 2022 at 21:54
  • $\begingroup$ Let's say I want to replace a letter in the tape, for example, I replaced $\check{x}$ with $a$ and moved right then I pop $\check{x}$ from the right stack and push $a$ to the left stack? $\endgroup$
    – Mohamad S.
    May 9, 2022 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.