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 is empty and rejects otherwise.
Using , build another TM as follows
On input ,
- Construct a new TM as follows
- On input
- If , reject.
- If , run on . If accepts , accept.
- Run on . If accepts, reject. If rejects, accept.
Notice the language of the TM . If accepts , . If does not accept , .
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.