Original title: Problém Busy Beaver
Translated title: Busy Beaver Problem
Authors: Kropitz, Pavel ; Holan, Tomáš (advisor) ; Mráz, František (referee)
Document type: Bachelor's theses
Year: 2011
Language: slo
Abstract: [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.
Keywords: busy beaver; induction; non-halting decision; proof; busy beaver; dôkaz; indukcia; rozhodnutie nezastavenia

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/37142

Permalink: http://www.nusl.cz/ntk/nusl-301406


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses