Share
Explore BrainMass

2DIM-DFA is undecidable

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.

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