Undecidable Language : ETM

Consider the following language

$\begin{equation*} E_{TM} = \{ <M>: M \text{ is a TM and with } L(M) = \emptyset \} \end{equation*}$

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

Suppose to the contrary that that there exists a TM, $F$ , that decides $E_{TM}$ . This machine takes $<M>$ as an input. It accepts if $L(M)$ is empty and rejects otherwise.

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

On input $<M, w>$ ,

Construct a new TM as follows
1. On input $<x>$
2. If $x != w$ , reject.
3. If $x == w$ , run $M$ on $w$ . If $M$ accepts $w$ , accept.
Run $F$ on $<C>$ . If $F$ accepts, reject. If $F$ rejects, accept.

Notice the language of the TM $C$ . If $M$ accepts $w$ , $L(C) = \{w\}$ . If $M$ does not accept $w$ , $L(C) = \emptyset$ .

Visualizing $D$ . The blue shaded box is $C$ . The grey shaded box is $F$ .

The machine $D$ takes $<M, w>$ as an input. It accepts if $M$ accepts $w$ and rejects if $M$ does not accept $w$ . In essence, this is a machine that decides $A_{TM}$ . We say that $A_{TM}$ reduces to $E_{TM}$ .

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

The Beard Sage

Undecidable Language : E_TM

Leave a Reply Cancel reply