Universální Turingův stroj

• Název práce v češtině: Universální Turingův stroj
• Název v anglickém jazyce: Universal 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í: 05.11.2009
• Datum zadání: 05.11.2009
• Datum a čas obhajoby: 25.06.2010 00:00
• Datum odevzdání elektronické podoby: 25.06.2010
• Datum proběhlé obhajoby: 25.06.2010
• Oponenti: Mgr. et Mgr. Emil Jeřábek, Dr., Ph.D.

Zásady pro vypracování

Nastudovat a presentovat konstrukce universálního Turingova stroje
a případně navrhnout vlastni konstrukci.

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

Konstrukce universálního Turingova stroje.

Předběžná náplň práce v anglickém jazyce

Constructions of Universal Turing machines.