2.3. Univerzális Turing-gép

Egy megfelelő nyelvet használva tetszőleges T Turing-gép leírható egy wT karaktersorozattal, s létezik egy olyan U Turing gép, hogy az U pontosan akkor fogadja el a wT , s inputot, amikor a T elfogadja az s inputot; feltéve, hogy a wT egy Turinggép kódja. Miután az U Turing-gép képes szimulálni minden Turing-gépet, ezért Univerzális Turing-gépnek nevezzük. (A konkrét konstrukció több szakkönyben is megtalálható, mi most nem részletezzük.)

Tétel. Létezik felsorolható, de nem rekurzív nyelv.

Bizonyítás: Tekintsük azokat a Turing-gépeket, melyek nem fogadják el a saját kódjukat inputként. Ezen Turing-gépek kódjai meghatároznak egy nyelvet. Erről a nyelvről belátható, hogy rekurzív felsorolható, ám ezzel mi nem foglalkozunk. Ha ez a nyelv még rekurzív is volna, akkor lenne egy Turing gép, amely pontosan ezt a nyelvet ismerné fel. Azaz azokat a kódokat ismerné fel, amelyhez tartozó Turinggépek nem ismerik fel magukat. Felismeri-e ez a gép saját magát? Ha nem, akkor kódja benne van a nyelvben, de akkor a definíció miatt fel kellene ismernie saját magát. Ha pedig felismeri, akkor olyan a kódja, hogy nem ismerheti fel magát. Mindkét esetben ellentmondáshoz jutottunk, így ez a nyelv nem lehet rekurzív.

Eldöntési probléma. Tetszőleges Turing-gép kódjára és tetszőleges inputra el tudja- e dönteni az univerzális gép, hogy a szimulált gép megáll-e az adott inputra, vagy sem? Miután felsorolhatóak azok a Turing-gép kódokból és megfelelő inputból álló párok, melyekre a szimulált gép megáll, ezen párok nyelvéhez létezik azt felismerő Turing-gép, s a párok nyelve rekurzív felsorolható. Ha ez a nyelv még rekurzív is lenne, a megfelelő Turing gép eldöntené az önmagukat fel nem ismerő gépek problémáját, felismerné az előbbi nyelvet is, de az meg kizárt.