Problém Busy Beaver

• Thesis title in thesis language (Slovak): Problém Busy Beaver
• Thesis title in Czech: Problém Busy Beaver
• Thesis title in English: Busy Beaver Problem
• Key words: busy beaver, dôkaz, indukcia, rozhodnutie nezastavenia
• English key words: busy beaver, proof, induction, non-halting decision
• Academic year of topic announcement: 2007/2008
• Thesis type: Bachelor's thesis
• Thesis language: slovenština
• Department: Department of Software and Computer Science Education (32-KSVI)
• Supervisor: RNDr. Tomáš Holan, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 02.11.2007
• Date of assignment: 02.11.2007
• Date and time of defence: 09.02.2011 09:00
• Date of electronic submission: 10.12.2010
• Date of submission of printed version: 10.12.2010
• Date of proceeded defence: 09.02.2011
• Opponents: RNDr. František Mráz, CSc.

Guidelines

Cílem práce je vyvinout a implementovat optimalizační metody
procházení prostoru, odhalování cyklů atd., nad Turingovými stroji,
které by našly uplatnění při řešení otevřeného problému Busy Beaver řádu 5+.

Výsledkem bude program prohledávající prostor Turingových strojů s nejméně pěti stavy
a simulátor Turingových strojů podrobně zobrazující výpočet už konkrétního, zvoleného stroje.

References

[1] Radó, Tibor (1962), On non-computable functions,
Bell Systems Tech. J. 41, 3 (May 1962)

[2] Lin, Shen and Radó, Tibor (1965), Computer Studies of Turing Machine Problems,
Journal of the Association for Computing Machinery, Vol. 12, No. 2
(April 1965), pp. 196-212

[3] Machlin, Rona and Stout, Quentin F. (1990), The complex behavior of simple machines,
Physica D, No. 42 (June 1990), pp. 85-98.

[4] Marxen, Heiner and Buntrock, Jürgen (1990), Attacking the Busy Beaver 5,
Bulletin of the EATCS, No 40 (February 1990), pp. 247-251.

[5] Alex Holkner, Acceleration Techniques for Busy Beaver Candidates,
in Gad Abraham and Benjamin I.P. Rubenstein (eds.),
Proceedings of the Second Australian Undergraduate Students’ Computing Conference
pp. 75-80, December, 2004. ISBN 0-975-71730-8.
Available from http://www.cs.berkeley.edu/~benr/publications/auscc04.

Preliminary scope of work

Optimalizační metody procházení prostoru, odhalování cyklů atd., nad Turingovými stroji,
které by našly uplatnění při řešení otevřeného problému Busy Beaver řádu 5+.
Program prohledávající prostor Turingových strojů s nejméně pěti stavy
a simulátor Turingových strojů podrobně zobrazující výpočet už konkrétního, zvoleného stroje.

Preliminary scope of work in English

Optimalization methods for searching space of TM(5), using proofs,
applicable for solving the Busy Beaver Problem.
Implementation of those methods.