Univerzális Turing gép
Legyen m az input, p pedig az n-ik Turing gép erre adott outputja:
Tn(m) = p
Értelmezzük a feladatot úgy, hogy a Turing gépek definíciója egy olyan algoritmus, amely megadja, mi az eredménye a fenti n,m számpárnak. Ez az algoritmus legyen az univerzális Turing-gép, jele U. Ennek a szalagon egy számpárt kell megadnunk, a szimulálandó Turing gép sorszámát, és annak az inputját.
U(n,m) = p
Ez a gép természetesen megadható, mint egy Turing gép, sorszáma is van. (Ez a bevezetett jelöléseinket alkalmazva egy decimálisan 180 jegyû szám)
U(n,m) = Tn(m)
3. Univerzális Turing-gép
Egy megfelelo nyelvet használva tetszoleges 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. Errol a
nyelvrol 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. Tetszoleges Turing-gép kódjára és tetszoleges 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 megfelelo inputból álló
párok, melyekre a szimulált gép megáll, ezen párok nyelvéhez létezik azt felismero
Turing-gép, s a párok nyelve rekurzív felsorolható. Ha ez a nyelv még rekurzív
is lenne, a megfelelo Turing gép eldöntené az önmagukat fel nem ismero gépek
problémáját, felismerné az elobbi nyelvet is, de az meg kizárt.