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 and rejects otherwise.
Using , build another TM as follows
- Construct a new TM which rejects everything.
- Run on . If accepts, accept. If rejects, reject.
Notice the language of the TM is empty. If accepts , then the language of is also empty.
The machine takes as an input. It accepts if and rejects otherwise. 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.