Uniqueness of computability structures

Struktura izračunljivosti na metričkom prostoru je skup nizova s određenim svojstvima koji nam omogućava da klasične koncepte teorije izračunljivosti prenesemo u proizvoljan metrički prostor. U disertaciji će poseban naglasak biti na strukturama izračunljivosti koje su maksimalne s obzirom na inkluziju te strukturama izračunljivosti koje sadrže gust niz, to jest separabilnim strukturama izračunljivosti. Svaka separabilna struktura izračunljivosti je maksimalna, no obrat općenito ne vrijedi. U radu će se precizno opisati maksimalne strukture na euklidskom prostoru \(\mathbb{R}^n\) te će biti dokazano da je svaka maksimalna struktura izračunljivosti na nekom podskupu od \(\mathbb{R}^n\) zapravo izometrična slika strukture izračunljivosti koja se sastoji od izračunljivih nizova u \(\mathbb{R}^n\), to jest kanonske strukture izračunljivosti. Iz te veze maksimalnih i kanonskih struktura slijedit će da je svaka maksimalna struktura izračunljivosti na \(\mathbb{R}^n\) separabilna. Nadalje, u disertaciji ćemo se fokusirati i na pronalaženje uvjeta pod kojima je separabilna struktura izračunljivosti na metričkom prostoru jedinstvena ili jedinstvena do na izometriju. Pri tome ćemo se ograničiti na efektivno kompaktne metričke prostore. Općenito pitanje je povlači li efektivna kompaktnost metričkog prostora njegovu izračunljivu kategoričnost. Poznato je da je odgovor potvrdan u slučaju kada postoji samo konačno mnogo izometrija tog prostora. U disertaciji ćemo taj rezultat proširiti dokazom da ako dva efektivna separirajuća niza dijele izračunljiv skup za koji postoji samo konačno mnogo izometrija prostora koje ga fiksiraju, tada ta dva niza moraju biti ekvivalentna. Osim toga, dokazat ćemo da je orbita izračunljive točke pri djelovanju grupe izometrija koizračunljivo prebrojiv skup te ćemo to iskoristiti kako bismo dokazali da su određeni efektivno kompaktni podskupovi euklidskog prostora izračunljivo kategorični. Iz tih rezultata slijedit će da na podskupovima od \(\mathbb{R}^2\) i \(\mathbb{R}^3\) efektivna kompaktnost zaista povlači izračunljivu kategoričnost. Na kraju ćemo se baviti prostorima koji su efektivno kompaktni čim na njima postoji efektivan separirajući niz, to jest kategorički efektivno kompaktnim prostorima. Pokazat ćemo kako je pitanje kategoričke efektivne kompaktnosti povezano s pitanjem povlači li izračunljiva prebrojivost skupa njegovu izračunljivost te ćemo dokazati kategoričku efektivnu kompaktnost rubova otvorenih omeđenih konveksnih skupova u \(\mathbb{R}^n\)A computability structure on a metric space is a set of sequences with certain properties that enables us to introduce classical concepts of computability theory into an arbitrary metric space. In the dissertation, special emphasis will be on computability structures that are maximal with respect to inclusion and computability structures that contain a dense sequence, i.e. separable computability structures. Any separable computability structure is maximal, but the converse is in general not true. In the dissertation, maximal computability structures on Euclidean space \(\mathbb{R}^n\) will be described precisely and it will be proved that any maximal computability structure on a subset of \(\mathbb{R}^n\) is actually an isometric image of the computability structure which consists of computable sequences in \(\mathbb{R}^n\), i.e. canonical computability structure. From that bond between maximal and canonical computability structures, it will follow that any maximal computability structure on \(\mathbb{R}^n\) is separable. We will also focus on finding the conditions under which a separable computability structure on a metric space is unique or unique up to an isometry. In doing so, we will limit ourselves to effectively compact metric spaces. A general question is whether effective compactness of a metric space implies its computable categoricity. It is known that this implication is true for metric spaces which have only finitely many isometries. In the dissertation we will expand that result with the fact that if two effective separating sequences share a computable set which has the property that there are only finitely many isometries of the underlying space which fix that set, then the sequences have to be equivalent. Moreover, we will prove that the orbit of a computable point under the isometry group is a co-computably enumerable set and we will use this to prove that certain effectively compact subsets of Euclidean space are computably categorical. From these results, it will follow that in \(\mathbb{R}^2\) and \(\mathbb{R}^3\) effective compactness implies computable categoricity. Lastly, we will examine spaces which are effectively compact if they contain at least one effective separating sequence, i.e. categorically effectively compact spaces. We will show how the question of categorical effective compactness is connected to the question whether computable enumarability of a set implies its computability and we will show categorical effective compactness for boundaries of open bounded convex subsets of \(\mathbb{R}^n\)