Turingův stroj: Porovnání verzí

''Univerzální Turingův stroj'' je takový TS ''U'', který jako vstup přijímá kód jiného TS ''T'' (jeho [[Gödelovo číslo]]) a vstupní slovo stroje ''T''. Dokáže rozkódovat přechodovou funkci stroje ''T'' a výpočet tohoto stroje simulovat. Univerzální TS dokáže vypočítat libovolnou [[částečně rekurzivní funkce|částečně rekurzivní funkci]] (neboli je ekvivalentní k univerzální částečně rekurzivní funkci), rozhoduje jakýkoliv [[rekurzivní jazyk]] a přijímá libovolný [[rekurzivně spočetný jazyk]].

 

 

{{pahýl}}