5.2. Diagonal language

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.