Undecidable Language : EQTM

Consider the following language

    \begin{equation*} EQ_{TM} = \{ <M_1, M_2>: M_1 \text{ and } M_2 \text{ are TMs with } L(M_1) = L(M_2) \} \end{equation*}

EQ_{TM} is undecidable. This can be proved using contradiction.

Suppose to the contrary that that there exists a TM, Q, that decides EQ_{TM}. This machine takes <M_1, M_2> as an input. It accepts if L(M_1) = L(M_2) and rejects otherwise.

Visualizing Q

Using Q, build another TM D as follows

On input <M>

  1. Construct a new TM N which rejects everything.
  2. Run Q on <M, N>. If Q accepts, accept. If Q rejects, reject.

Notice the language of the TM N is empty. If Q accepts <M, N>, then the language of M is also empty.

Visualizing D. The shaded blue box is N. The shaded grey box is Q.

The machine D takes <M> as an input. It accepts if L(M) = \emptyset and rejects otherwise. In essence, this is a machine that decides E_{TM}. We say that E_{TM} reduces to EQ_{TM}.

If EQ_{TM} is decidable, this makes E_{TM} decidable as well. This is a contradiction. Since E_{TM} is undecidable, EQ_{TM} is also undecidable.

Leave a Reply

Your email address will not be published. Required fields are marked *