Undecidable Language : HALTTM

Consider the following language

    \begin{equation*} HALT_{TM} = \{ <M, w>: M \text{ is a TM and halts on input } w \} \end{equation*}

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

Suppose to the contrary that that there exists a TM, C, that decides HALT_{TM}. This machine takes <M, w> as an input. It accepts if M halts on input w and rejects if M does not halt on input w.

Visualizing C

Using C, build another TM D as follows

On input <M, w>

  1. Run C on <M, w>. If C rejects, reject.
  2. If C accepts, run M on w. If M accepts w, accept. Else if M rejects w, reject.
Visualizing D. The shaded box is C.

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 HALT_{TM}.

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

Leave a Reply

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