5.2. A diagonális nyelv

A későbbiekben szükségünk lesz egy különleges nyelvre. Ez az úgynevezett diagonális nyelv.

5.5. Definíció

Legyen 
                  
                azon szavak nyelve, amelyek Turing-gép programok, és a 
hozzájuk tartozó Turing-gép nem fogadja el őket. Formálisan:

            

Az így megadott nyelvet diagonális nyelvnek nevezzük. A diagonális nyelv definíciója meglehetősen különleges tulajdonságokat sugall. Itt a nyelv egy elemét egyszerre tekintjük feladatnak és algoritmusnak is. Ráadásul azzal a nyakatekert tulajdonsággal, hogy saját magát mint feladatot az algoritmus nem tudja megoldani.