Explore BrainMass
Share

# 2DIM-DFA is undecidable

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

The language define by the equality of two 2DIM-DFA machines on all inputs is undecidable. The full definition of 2DIM-DFA can be found in Sipser's "Introduction to the Theory of Computation" (5.17)

I show a reduction to the decidability of a problem which is known to be undecidable and hence prove the undecidability of the original language.

https://brainmass.com/computer-science/programming-languages/122400

#### Solution Preview

We define the language
EQ-2DIM-DFA = {<M1,M2> , M1,M2 are 2DIM-DFA | L(M1)=L(M2)}

Recall that ELBA = {<M> | M is an LBA and L(M) is empty} is un-decidable.
We will reduce ELBA to EQ-2DIM-DFA by showing that if EQ-2DIM-DFA is decidable than so is ELBA.
We first show how to ...

#### Solution Summary

The language defined by the equality of two 2DIM-DFA machines on all inputs is undeciable. The full definition of 2DIM-DFA can be found in Sipser's "Introduction to the Theory of Computation" (5.17)

I show a reduction to the decidability of a problem which is known to be undecidable and hence prove the undecidability of the original language.

\$2.19