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

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

On input $<M>$

Run $H$ on $<M, <M>>$ .
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>$

Run $M$ on $w$ .
If $M$ accepts, accept.

Undecidable Language : A_TM

Leave a Reply Cancel reply