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,

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

Proof

This proof involves using set operations (specifically, ones that preserve regularity) on $M$ and $N$ to get the empty set, $\varnothing$. Then, the problem reduces to the emptiness problem, 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 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 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

We use a simple proof by reduction:

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