20.500.12556/RUL-106821 Königova lema in Kleenejevo drevo delo diplomskega seminarja König's lemma and Kleene tree V delu predstavimo neskončna dvojiška drevesa in neskončne poti v drevesih. Definiramo Cantorjev prostor kot produkt števno neskončno kopij diskretnega prostora 2 = {0, 1}. Na kratko predstavimo Turingove stroje in izračunljivo analizo, v kateri vsako računanje opravimo z mehansko napravo (v našem primeru s pomočjo Turingovih strojev). Spoznamo, da je šibka Königova lema na dvojiških drevesih, v navadni matematiki kot tudi v izračunljivi, zelo močno orodje. Konstruiramo takšno izračunljivo neskončno dvojiško drevo, ki nima izračunljive neskončne poti, to je Kleenejevo drevo. S pomočjo Kleenejevega drevesa dokažemo še, da izračunljiv Cantorjev prostor in izračunljiv interval nista izračunljivo kompaktna. In this work, we present infinite binary trees and infinite paths in them. We define the Cantor space as a product of countably many copies of the discrete space 2 = {0, 1}. We briefly introduce Turing machines and computability, where each calculation is done with a mechanical device (in our case, with the help of Turing machines). We notice that the weak König's lemma on binary trees is a very powerful tool in ordinary mathematics as well as in computability theory. We construct an infinite computable tree that does not have an infinite computable path, that is Kleene tree. Using Kleene tree, we also prove that the computable Cantor space and the computable interval are not compact in a computable way. dvojiško drevo Cantorjev prostor Königova lema teorija izračunljivosti Kleenejevo drevo binary tree Cantor space König's lemma computability theory Kleene tree true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2019-03-18 12:02:00 2019-03-18 12:02:01 2024-05-30 12:14:09 0000-00-00 00:00:00 2019 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 510.6 95746 18602585 630.pdf 630.pdf 1 F89A2F9C155EA10D181DE0E396E9BBBD 3d02da639850cb3309bf392d9c9677a0308e831d0965ee7bd8b016816bbe95da 60e64ce9-a1b6-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=117574 Fakulteta za matematiko in fiziko 0 0 0