Undecidable Language : ATM

Consider the following language

    \begin{equation*} A_{TM} = \{ <M, w>: M \text{ is a TM and } w \in L(M) \} \end{equation*}

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

Suppose to the contrary that that there exists a TM, H, that decides A_{TM}. This machine takes <M, w> as an input. It accepts if M accepts w and rejects if M does not accept w.

Visualizing H

Using H, build another TM D as follows

On input <M>

  1. Run H on <M, <M>>.
  2. If H accepts, reject. If H rejects, accept.

Notice that <M> is the string encoding of a machine and can be used as the w argument to <M, w>.

Visualizing D. The shaded box is H.

The machine D takes <M> as an input. It accepts if M does not accept <M> and rejects if M accepts <M>.

However, this leads to a contradiction. If D is fed the input <D>, it accepts if D does not accept <D> and rejects if D accepts <D>.

This contradiction implies that D cannot and consequently H cannot exist. The assumption that there exists a machine to decide A_{TM} was wrong. Thus A_{TM} is undecidable.

However, A_{TM} is recognizable.

On input <M, w>

  1. Run M on w.
  2. If M accepts, accept.

Leave a Reply

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