|
|
Universal Turing machine
Bahýľ, Viktor ; Krajíček, Jan (vedoucí práce) ; Holub, Štěpán (oponent)
Název práce: Univerzální Turingův stroj Autor: Viktor Bahýľ Katedra: Katedra Algebry Vedoucí bakalářské práce: prof. RNDr. Jan Krajíček, DrSc., Katedra algebry Abstrakt: Práce se zaměřuje na problematiku výpočetních úloh a jejich řešení. Na jejich řešení lze využít model Turingova stroje, který je plnou náplní této práce. Pro samotné řešení problémů je důležitá obecnost daného mechanismu, která je v teorií Turingova strojů zastoupena v podobě jejich univerzálnosti, která spojuje pojmy simulace a reprezentace. Hlavním výsledkem a úkolem práce je formulovat univerzální Turingův stroj a následně o něm tuto univerzálnost dokázat. V úvodních částech práce se nacházejí teoretické definice potřebné pro práci s těmito metodami řešení výpočetních úloh. Jako klíčové se ukáží již zmíněné pojmy simulace Turingových strojů a jejich reprezentace. Na oba pojmy je kladen samostatný důraz a snaha o co nejlepší vysvětlení těchto pojmů. V práci se pracuje s vlastní formou reprezentace, která je podrobně popsána a s nadefinovaným Turingovým strojem, jehož definice je také podrobně popsána, spolu s kompletním důkazem o univerzálnosti tohoto stroje. Klíčová slova: Turing, stroj, univerzálnost, reprezentace
|
host ::
RSS.