Equivalence Problem

The Equivalence problem is a decision problem asks if any two machines $M$ and $N$ are equivalent.

Problem Specification(s) §

General §

Given any two machines $M$ and $N$, are they both equivalent? That is, is $L(M)=L(N)$?

Decidability §

The decidability of the problem requires a restructuring. Let $E{Q}_k$ be a language given by the TM encoding of $M$

$$E{Q}_k=\{⟨M,N⟩|\text{M,N are machines of type k where L(M)=L(N)}\}$$

Then, we need to check if $E{Q}_k$ is T-decidable.

The FSA Equivalence Problem is decidable ^theorem-fsa

That is,

EQ_{FSA} = { \langle M,N \rangle \ \vert \ \text{$M,N$ are FSAs such that $L(M)=L(N)$} } \text{ is T-decidable}

>[!example]- Proof >This proof involves using [set operations](Set%20Operations.md) (specifically, ones that [preserve regularity](Regular%20Language.md#Regular%20Operations)) on $M$ and $N$ to get the empty set, $\varnothing$. Then, the problem reduces to the [emptiness problem](Emptiness%20Problem.md), which is decidable. > >* We know that if $L(M) = L(N)$, then there should be no set difference between them. That is $L(M)\setminus L(N) = L(N)\setminus L(M) = \varnothing$ >* Since the set difference is a regularity-preserving operation, and $L(M)$ and $L(N)$ are regular by definition, then their set difference can be constructed, is regular, and thus has a corresponding [DFA](Deterministic%20Finite%20Automaton.md) that recognises it. >* We can then use the union (again, a regular operation) to get a DFA, $P$ that recognises: >$$ >\text{$P$ recognises } (L(M) \setminus L(N)) \cup (L(N) \setminus N(M)) = \varnothing >$$ >* Then, this is a [reduction](Proof%20By%20Reduction.md) to the emptiness problem for $P$, which is decidable.

The TM Equivalence Problem is undecidable ^theorem-tm

$$E{Q}_{TM}=\{⟨M,N⟩|\text{M,N are TMs such that L(M)=L(N)}\}\text{ is T-decidable}$$

Proof proof by reduction:

We use a simple

• The emptiness problem reduces to equivalence problem
• The emptiness problem is undecidable
• Hence, the equivalence problem is also undecidable