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

On input

- 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.