Effective compactness

U ovom dipomskom radu proučavamo izračunljive metričke prostore. Posebnu pažnju pridajemo takozvanim efektivno kompaktnim izračunljivim metričkim prostorima. U prvom poglavlju obrađujemo teoriju izračunljivosti. Uvodimo pojam rekurzivne funkcije, rekurzivnog skupa i rekurzivnog prebrojivog skupa. Također, proširujemo pojam rekurzivne funkcije na kodomene \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}\)te dokazujemo neke važne rezultate koji će nam biti potrebni. Obrađujemo još i r.r.o. funkcije koje će se pokazati vrlo korisne pri dokazivanju rezultata vezanih za efektivnu kompaktnost. U drugom poglavlju bavimo se izračunljivim metričkim prostorima. Obrađujemo pojam izračunljivo prebrojivog skupa i izračunljivog skupa u izračunljivom metričkom prostoru. Dokazujemo da se izračunljivi skupovi u izračunljivom metričkom prostoru mogu promatrati i sami kao izračunljivi metrički prostori. Također, pokazujemo da svaki izračunljiv metrički prostor na svojevrstan način inducira novi izračunljiv metrički prostor, kojeg nazivamo hiperprostorom. U trećem poglavlju posvećujemo se efektivno kompaktnim izračunljivim metričkim prostorima. Navodimo neke važne primjere. Dokazujemo da su izračunljivi skupovi gledani kao izračunljivi metrički prostori efektivno kompatkni te dokazujemo i svojevrstan obrat te tvrdnje. Glavni rezultat kojeg dokazujemo je da efektivna kompaktnost ne ovisi o efektivnom separirajućem nizu.In this thesis we study computable metric spaces. Special attention is paid to the so-called effectively compact computable metric spaces. In the first chapter, we study the theory of computability. We introduce the concept of recursive function, recursive set and recursevly enumerable set. Also, we extend the notion of recursive function to codomains \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}\) and prove some important results that we will need. We also study r.r.b. functions, which will prove to be very useful in proving results related to effective compactness. In the second chapter we study computable metric spaces. We analyze the notion of a computably enumerable set and a computable set in a computable metric space. We prove that computable sets in a computable metric space can be viewed as computable metric spaces themselves. Also, we show that every computable metric space in a particular way induces a new computable metric space, which we call a hyperspace. In the third chapter, we devote ourselves to effectively compact computable metric spaces. We state some important examples. We prove that computable sets viewed as computable metric spaces are effectively compact and we also prove a kind of reversal of that claim. The main result we prove is that the effective compactness does not depend on the effective separating sequence