Computation history method

ᴬ In the proof of Theorem 5.15, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the PCP construction to handle this case.

Define a two-headed finite automaton (2DFA) to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a 2DFA is finite and is just large enough to contain the input plus two additional blank tape cells, one on the left-hand end and one on the right-hand end, that serve as delimiters. A 2DFA accepts its input by entering a special accept state. For example, a 2DFA can recognize the language $\left\{ \mathrm{a}^{n} \mathrm{~ b}^{n} \mathrm{c}^{n} \mid n \geq 0\right\}$.

A two-dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an $m \times n$ rectangle, for any $m, n \geq 2$. The squares along the boundary of the rectangle contain the symbol and the internal squares contain symbols over the input alphabet $\Sigma$. The transition function $\delta : Q \times (\Sigma \cup \left\{ \# \right\} ) \longrightarrow Q \times \left\{ \mathrm{L}, \mathrm{R}, \mathrm{U}, \mathrm{D}\right\}$ indicates the next state and the new head position (Left, Right, Up, Down). The machine accepts when it enters one of the designated accept states. It rejects if it tries to move off the input rectangle or if it never halts. Two such machines are equivalent if they accept the same rectangles. Consider the problem of determining whether two of these machines are equivalent. Formulate this problem as a language and show that it is undecidable.

Consider the problem of determining whether a PDA accepts some string of the form $\left\{ w w \mid w \in \left\{ 0,1\right\}^{*}\right\}$. Use the computation history method to show that this problem is undecidable.