20.500.12556/RUL-96681 Neodločljivi problemi v teoriji izračunljivosti Undecidable problems in the theory of computation V magistrskem delu je predstavljena hierarhija avtomatov in pripadajočih jezikov. Vpeljani so pojmi, povezani z razpoznavnimi in nerazpoznavnimi jeziki. Sledi nadaljnja vpeljava podrazreda razpoznavnih jezikov; to so odločljivi jeziki. S pomočjo odločljivih oziroma neodločljivih jezikov prevedemo in strogo definiramo koncept odločljivih oziroma neodločljivih problemov. Podrobno so opisani so naslednji zgledi neodločljivih problemov: problem zaustavitve Turingovega stroja, Postov korespodenčni problem, problem zaposlenega bobra in Hilbertov deseti problem. V okviru magistrskega dela je bila izdelana spletna aplikacija, ki išče konkretne rešitve Postovega korespodenčnega problema. Podrobno je opisano programsko orodje z razlago programske kode in navodili za uporabo. Naveden je tudi primer uporabe spletne aplikacije v praksi, na primer pri računalniškem krožku. In this master thesis the hierarchy of automata and related languages is presented. First, the concepts, associated with recognizable and unrecognizable languages are introduced, followed by further introduction of a subclass of recognized languages; these are decidable languages. By means of decidable and undecidable languages the concept of decidable and undecidable problems was translated and strictly defined. The following examples of undecidable problems are described in detail: the Turing's halting problem, the Post correspondence problem, the busy beaver problem and the Hilbert's tenth problem. In the frame of the master thesis, a web application which is searching for concrete solutions of the Post correspondence problem, was developed. The programming environment of the application and the interpretation of the source code with instructions for its using are described in detail. An example for the usage of the application at teaching, for example in a computer club, is presented. hierarhija avtomatov in jezikov hierarchy of automata and related languages true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2017-10-10 02:55:00 2017-10-11 15:21:04 2025-04-17 04:53:25 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 11768905 NeodlocljiviProblemiVteorijiIzracunljivosti_MagistrskoDelo_LukaViktorRogac.pdf NeodlocljiviProblemiVteorijiIzracunljivosti_MagistrskoDelo_LukaViktorRogac.pdf 1 9AF9A9D7EDE622A18DBC4F230E95ADCA e47eba7a77339c300da54ce418f555c72836e95a6821b344241c85c32012599f 5d7cd357-1aaf-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=205844 Pedagoška fakulteta 0 0 0