We will need a particular language, the so called diagonal language in the following.

**Definition 5.5.**

`Let `**
** be the language of Turing machine programs such that
the corresponding Turing machines do not accept themselves.
Formally:

The language defined above is called the diagonal language. Due to its definition, one may feel that it has some special properties. A word from the diagonal language is a program and an input in the same time. Furthermore, the algorithm cannot solve itself as a task.