| Popis: |
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. |
