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

On input

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