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 .
Using , build another TM as follows
- Run on . If rejects, reject.
- If accepts, run on . If accepts , accept. Else if rejects , reject.
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.