# 2DIM-DFA is undecidable

Not what you're looking for?

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.

##### Purchase this Solution

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

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

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

##### Basic Networking Questions

This quiz consists of some basic networking questions.

##### Javscript Basics

Quiz on basics of javascript programming language.

##### C++ Operators

This quiz tests a student's knowledge about C++ operators.

##### C# variables and classes

This quiz contains questions about C# classes and variables.