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$ .

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

On input $<M, w>$

Run $C$ on $<M, w>$ . If $C$ rejects, reject.
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.

Undecidable Language : HALT_TM

Leave a Reply Cancel reply