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 accepts and rejects if does not accept .

Using , build another TM as follows

On input

- Run on .
- If accepts,
*reject*. If rejects,*accept*.

Notice that is the string encoding of a machine and can be used as the argument to .

The machine takes as an input. It accepts if does not accept and rejects if accepts .

However, this leads to a contradiction. If is fed the input , it accepts if does not accept and rejects if accepts .

This contradiction implies that cannot and consequently cannot exist. The assumption that there exists a machine to decide was wrong. Thus is undecidable.

However, is recognizable.

On input

- Run on .
- If accepts,
*accept*.