Název: Problém Busy Beaver
Překlad názvu: Busy Beaver Problem
Autoři: Kropitz, Pavel ; Holan, Tomáš (vedoucí práce) ; Mráz, František (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2011
Jazyk: slo
Abstrakt: [eng] [cze]
The work's purpose was to develop and implement optimalization methods that could be used for solving Busy Beaver problem with order of 5+. The result of the work is the theoretical part and its implementation in form of two programs - simulator of Turing Machines which shows the computation of the machine in detail along with application of theory, and program searching the space of Turing Machines. The latter was ran for machines with four to six states. The quality of the methods was proven by small number of machines that the program could not detect and by nding a new record machine - candidate for 6-state Busy Beaver. Práca mala za úlohu vyvinúť a implementovať optimalizačné metódy, ktoré by našli uplatnenie pri riešení busy beaver problému rádu 5+. Výsledkom práce je teoretická časť a jej implementácia v podobe dvoch programov - simulátora turingových strojov podrobne zobrazujúceho výpočet stroja s aplikáciou teórie a programu prehľadávajúceho priestor turingových strojov. Ten bol spustený pre turingove stroje o štyroch až šiestich stavoch. Kvalitu metód preukázal malým počtom strojov, ktorých správanie nedokázal odhaliť a nájdením nového rekordného stroja - kandidáta na busy beavera rádu 6.
Klíčová slova: busy beaver; dôkaz; indukcia; rozhodnutie nezastavenia; busy beaver; induction; non-halting decision; proof

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/37142

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-301406


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce