Různé definice Turingova stroje
Název práce v češtině: | Různé definice Turingova stroje |
---|---|
Název v anglickém jazyce: | Various definitions of the Turing machine |
Akademický rok vypsání: | 2009/2010 |
Typ práce: | bakalářská práce |
Jazyk práce: | čeština |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | prof. RNDr. Jan Krajíček, DrSc. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 26.10.2009 |
Datum zadání: | 26.10.2009 |
Datum a čas obhajoby: | 24.06.2010 00:00 |
Datum odevzdání elektronické podoby: | 24.06.2010 |
Datum proběhlé obhajoby: | 24.06.2010 |
Oponenti: | prof. Mgr. Michal Koucký, Ph.D. |
Zásady pro vypracování |
Prostudovat a presentovat různé varianty definic Turingova stroje
a důkazy jejich ekvivalence, popřípadě navrhnout svoji definici. |
Seznam odborné literatury |
M. R. Garey, D. S. Johnson,
Computers and Intractability: A Guide to the Theory of NP-Completeness, FReeman, 1979. Turing, A.M. (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, 2 42: 230?65, 1937, doi:10.1112/plms/s2-42.1.230, http://www.comlab.ox.ac.uk/activities/ieg/e-library/sources/tp2-ie.pdf (and Turing, A.M. (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction", Proceedings of the London Mathematical Society, 2 43: 544?6, 1937, doi:10.1112/plms/s2-43.6.544 ) |
Předběžná náplň práce |
Práce zkoumá varianty Turingova stroje. |
Předběžná náplň práce v anglickém jazyce |
The project is concerned with variants of Turing machine
definitions. |