2.2. Church-Turing tézis

Ami algoritmussal kiszámítható, az Turing-értelemben kiszámítható:

– Az f parciális függvény akkor és csak akkor kiszámítható, ha f parciálisan rekurzív.

– Az f függvény akkor és csak akkor kiszámítható, ha f rekurzív.

– Az L nyelvhez tartozás problémája algoritmussal csak akkor és akkor eldönthető, ha L rekurzív.

Ezekben az állításokban két fajta kiszámíthatóságról esik szó. A Turing-értelemben kiszámíthatóság jól definiált fogalom, míg az algoritmussal kiszámíthatóság nem az. Ennek megfelelően ez a tétel nem bizonyítható, viszont a gyakorlati tapasztalatokkal egybevág.

Állítás. Van olyan nyelv, mely nem rekurzív felsorolható.

Bizonyítás: A Turing-gép végesen leírható, ennek megfelelően maximum megszámlálhatóan sok létezik, ezek pedig felsorolhatóak. Minden géphez egyértelműen tartozik egy rekurzív felsorolható nyelv, így ezek is felsorolhatóak. Konstruáljunk egy olyan nyelvet, amely mindegyiktől különbözik. A véges szavak is felsorolhatóak, így definiáljuk az új nyelvet úgy, hogy ha az első nyelvben szerepel — ebben a felsorolásban— az első szó, akkor az új nyelvben ne szerepeljen, s viszont. Hasonlóan a másodikra, és így tovább. Az új nyelv mindegyik korábbi nyelvtől különbözik, így nem rekurzív felsorolható.

2.2. táblázat - L' diagonális konstrukciója

 w1 w2 w3 w4 w5 w6 ...
L1 XX X X...
L2 X  X X...
L3  X X X...
L4 XXX  X...
L5 X XXX ...
........................
L' XXX X...