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.