Original title:
Univerzální Turingův stroj
Translated title:
Universal Turing machine
Authors:
Bahýľ, Viktor ; Krajíček, Jan (advisor) ; Holub, Štěpán (referee) Document type: Bachelor's theses
Year:
2019
Language:
slo Abstract:
[eng][cze] Title: Universal Turing machine Author: Viktor Bahýľ Department: Department of Algebra Supervisor: RNDr. Jan Krajíček, DrSc., Department of Algebra Abstract: This thesis is focused on the processes of solving computational problems. The Turing machine is an example of a model which we can use to solve these problems and these machines are the main objective of this Bachelor thesis. The generality of the model is important; it allows us to simulate any conceivable algorithm. In the theory of Turing machines, the generality is demonstrated by the construction of a universal Turing machine. This is the task of this Thesis: to define a universal Turing machine and to prove its universality. Key definitions, linked with the Turing machines, are recalled at the beginning of the Thesis. The simulation and representation of Turing machines will prove to be the key concepts. We make an extra effort to explain these fundamental notions. The thesis has its own form of representation and defined Turing machine with detailed descriptions for them, together with complete proof of the universality of the mentioned Turing machine. Keywords: Turing, machine, universality, representationNá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
Keywords:
machine; representation; Turing; universality; reprezentace; stroj; Turing; univerzálnost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/107697