<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:dc="http://purl.org/dc/elements/1.1/"><rdf:Description rdf:about="https://repozitorij.uni-lj.si/IzpisGradiva.php?id=106821"><dc:title>Königova lema in Kleenejevo drevo</dc:title><dc:creator>Slivnik,	Tadej	(Avtor)
	</dc:creator><dc:creator>Bauer,	Andrej	(Mentor)
	</dc:creator><dc:subject>dvojiško drevo</dc:subject><dc:subject>Cantorjev prostor</dc:subject><dc:subject>Königova lema</dc:subject><dc:subject>teorija izračunljivosti</dc:subject><dc:subject>Kleenejevo drevo</dc:subject><dc:description>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.</dc:description><dc:date>2019</dc:date><dc:date>2019-03-18 12:02:00</dc:date><dc:type>Delo diplomskega seminarja/zaključno seminarsko delo/naloga</dc:type><dc:identifier>106821</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>