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
halts on input
and rejects if
does not halt on input
.
![](http://thebeardsage.com/wp-content/uploads/2020/04/HaltTm1.png)
![Rendered by QuickLaTeX.com C](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-7b7439203c048812d290ee4262adf7d7_l3.png)
Using , build another TM
as follows
On input
- Run
on
. If
rejects, reject.
- If
accepts, run
on
. If
accepts
, accept. Else if
rejects
, reject.
![](http://thebeardsage.com/wp-content/uploads/2020/04/HaltTm2.png)
![Rendered by QuickLaTeX.com D](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-044dbea9fb8e8c710e6b075bd224e769_l3.png)
![Rendered by QuickLaTeX.com C](http://thebeardsage.com/wp-content/ql-cache/quicklatex.com-7b7439203c048812d290ee4262adf7d7_l3.png)
The machine takes
as an input. It accepts if
accepts
and rejects if
does not accept
. In essence, this is a machine that decides
. We say that
reduces to
.
If is decidable, this makes
decidable as well. This is a contradiction. Since
is undecidable,
is also undecidable.