velikost textu

Univerzálny Turingov stroj

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Univerzálny Turingov stroj
Název v češtině:
Univerzální Turingův stroj
Název v angličtině:
Universal Turing machine
Typ:
Bakalářská práce
Autor:
Bc. Viktor Bahýľ
Vedoucí:
prof. RNDr. Jan Krajíček, DrSc.
Oponent:
doc. Mgr. Štěpán Holub, Ph.D. et Ph.D.
Id práce:
200589
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra algebry (32-KA)
Program studia:
Matematika (B1101)
Obor studia:
Matematika pro informační technologie (MMIT)
Přidělovaný titul:
Bc.
Datum obhajoby:
19. 6. 2019
Výsledek obhajoby:
Dobře
Jazyk práce:
Slovenština
Klíčová slova:
Turing, stroj, univerzálnost, reprezentace
Klíčová slova v angličtině:
Turing, machine, universality, representation
Abstrakt:
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
Abstract v angličtině:
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, representation
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Bc. Viktor Bahýľ 1.47 MB
Stáhnout Abstrakt v českém jazyce Bc. Viktor Bahýľ 130 kB
Stáhnout Abstrakt anglicky Bc. Viktor Bahýľ 129 kB
Stáhnout Posudek vedoucího prof. RNDr. Jan Krajíček, DrSc. 56 kB
Stáhnout Posudek oponenta doc. Mgr. Štěpán Holub, Ph.D. et Ph.D. 104 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. David Stanovský, Ph.D. 152 kB