Question

Question: A two-dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an$\mathit{m}\mathbf{\times }\mathit{n}$ rectangle, for any $\mathit{m}\mathbf{,}\mathit{n}\mathbf{⩾}\mathbf{2}$. The squares along the boundary of the rectangle contain the symbol # and the internal squares contain symbols over the input alphabet $\mathit{\Sigma }$. The transition function$\mathbf{\delta }\mathbf{:}\mathbf{}\mathbf{Q}\mathbf{}\mathbf{\times }\mathbf{}\left(\Sigma \cup \left\{\#\right\}\right)\mathbf{\to }\mathbf{Q}\mathbf{}\mathbf{\times }\mathbf{}\left\{L,R,U,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.

Short answer

The language in given question is undecidable.

Step-by-step solution

Undecidable

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

Formulating language and proving it undecidable

In order to check undecidability of two-dimensional finite automaton $E_{2DIM-DFA}$, we have to reduce$A_{TM}$ by m into$E_{2DIM-DFA}$ using map reduction$M,w$ to $<B>$.

This means, if w is accepted by Turing Machine M, then language L(B) must be non-empty otherwise L(B) must be empty.

We can get this by making L(B) as set of accepting all the histories of TM M on w. B can be consider as matrix that represent computational history$C_1,C_2\dots ..C_K$ such as:$C_1$ is in first row,$C_2$ in second row and so on.

So for given rectangular matrix, will check initial configuration of TM M on w is in first row or not and last row is accepting or final configuration. B also works as checking of each row that must follow the previous row as according to TM M.

Now, if M accepts w, that means there exist an accepting configuration history of TM M on w and L(B) is non-empty.

But if L(B) is empty, there is no accepting configuration history of TM M on w.

Thus, m-reduction mapping from$A_{TM}$ to$E_{2DIM-DFA}$ is undecidable.