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
.
![](http://thebeardsage.com/wp-content/uploads/2020/04/TM1.png)
![Rendered by QuickLaTeX.com H](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-0db8ba9879ee0d3c86361040b3c6cfbc_l3.png)
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
.
![](http://thebeardsage.com/wp-content/uploads/2020/04/TM2.png)
![Rendered by QuickLaTeX.com D](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-044dbea9fb8e8c710e6b075bd224e769_l3.png)
![Rendered by QuickLaTeX.com H](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-0db8ba9879ee0d3c86361040b3c6cfbc_l3.png)
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.