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.

Visualizing F

Using F, build another TM D as follows

On input <M, w>,

  1. Construct a new TM C as follows
    1. On input <x>
    2. If x != w, reject.
    3. If x == w, run M on w. If M accepts w, accept.
  2. 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.

Leave a Reply

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