Consider the following language
is undecidable. This can be proved using contradiction.
Suppose to the contrary that that there exists a TM, , that decides
. This machine takes
as an input. It accepts if
accepts
and rejects if
does not accept
.


Using , build another TM
as follows
On input
- Run
on
.
- If
accepts, reject. If
rejects, accept.
Notice that is the string encoding of a machine and can be used as the
argument to
.



The machine takes
as an input. It accepts if
does not accept
and rejects if
accepts
.
However, this leads to a contradiction. If is fed the input
, it accepts if
does not accept
and rejects if
accepts
.
This contradiction implies that cannot and consequently
cannot exist. The assumption that there exists a machine to decide
was wrong. Thus
is undecidable.
However, is recognizable.
On input
- Run
on
.
- If
accepts, accept.