Problém Busy Beaver
| Název práce v jazyce práce (slovenština): | Problém Busy Beaver |
|---|---|
| Název práce v češtině: | Problém Busy Beaver |
| Název v anglickém jazyce: | Busy Beaver Problem |
| Klíčová slova: | busy beaver, dôkaz, indukcia, rozhodnutie nezastavenia |
| Klíčová slova anglicky: | busy beaver, proof, induction, non-halting decision |
| Akademický rok vypsání: | 2007/2008 |
| Typ práce: | bakalářská práce |
| Jazyk práce: | slovenština |
| Ústav: | Katedra softwaru a výuky informatiky (32-KSVI) |
| Vedoucí / školitel: | RNDr. Tomáš Holan, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 02.11.2007 |
| Datum zadání: | 02.11.2007 |
| Datum a čas obhajoby: | 09.02.2011 09:00 |
| Datum odevzdání elektronické podoby: | 10.12.2010 |
| Datum odevzdání tištěné podoby: | 10.12.2010 |
| Datum proběhlé obhajoby: | 09.02.2011 |
| Oponenti: | RNDr. František Mráz, CSc. |
| Zásady pro vypracování |
| 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. |
| Seznam odborné literatury |
| [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. |
| Předběžná náplň práce |
| 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. |
| Předběžná náplň práce v anglickém jazyce |
| Optimalization methods for searching space of TM(5), using proofs,
applicable for solving the Busy Beaver Problem. Implementation of those methods. |