Univerzális Turing gép
A Turing-gép egy univerzális Turing - gép , amely bármely Turing-gépet helyettesíthet. Miután megkapta a programot és a bemeneti adatokat bemenetként, kiszámítja azt a választ, amelyet a bemeneti adatokból a Turing-gép, amelynek programját bemenetként adtuk meg.
Formális definíció
Bármely determinisztikus Turing-gép programja felírható valamilyen véges ábécé segítségével, amely állapotszimbólumokból, zárójelekből, nyilakból és így tovább; Jelöljük ezt a gépábécét . Ekkor egy univerzális U Turing-gép egy ábécével és k bemeneti szalaggal rendelkező gépek osztályához egy k + 1 beviteli szalaggal és olyan ábécével rendelkező Turing-gép, hogy ha az első k szalagnak bemeneti értéket adunk, és k + 1 -et kapunk. valamelyik Turing-gép helyesen megírt kódja , akkor U ugyanazt a választ adja, mint ezen a bemeneten , vagy korlátlanul fog futni, ha nem áll meg ennél a bemenetnél.
Az univerzális Turing-gép-tétel kimondja, hogy létezik ilyen gép, és más gépeket modellez legfeljebb másodfokú lassítással (tehát ha az eredeti gép t lépést tett meg, akkor az univerzális gép legfeljebb ct² ). Ennek a tételnek a bizonyítása konstruktív (egy ilyen gépet könnyű megépíteni, csak gondosan le kell írni). A tételt Turing javasolta és bizonyította 1947 - ben .