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.

Using $Q$ , build another TM $D$ as follows

On input $<M>$

Construct a new TM $N$ which rejects everything.
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.

The Beard Sage

Undecidable Language : EQ_TM

Leave a Reply Cancel reply