Topološki prostori izračunljivog tipa

master's thesis

• Author: Matea Čelar
• Mentor: Zvonko Iljazović (mentor)
• Committee member: Zvonko Iljazović (predsjednik povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Vedran Čačić (član povjerenstva)
• Committee member: Slaven Kožić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2019-09-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu proučavamo izračunljivost poluizračunljivih skupova u izračunljivim metričkim prostorima. Rad je podijeljen u četiri poglavlja. U prvom poglavlju generaliziramo teoreme klasične teorije izračunljivosti na funkcije s kodomenama \(\mathbb{Z}, \mathbb{Q}\) i \(\mathbb{R}\), te dokazujemo tehničke rezultate koji će nam biti korisni u kasnijim razmatranjima. U drugom poglavlju definiramo izračunljiv metrički prostor i uvodimo osnovne pojmove vezane uz izračunljivost u metričkom prostoru. Proučavamo izračunljivo prebrojive, izračunljive, poluizračunljive i koizračunljivo prebrojive skupove. Dokazujemo da je kompaktan skup u izračunljivom metričkom prostoru izračunljiv ako i samo ako je poluizračunljiv i izračunljivo prebrojiv. Glavni dio rada je treće poglavlje, u kojem dokazujemo izračunljivost nekih poluizračunljivih skupova u izračunljivom metričkom prostoru. Konkretno, dokazujemo da je poluizračunljiv lančast kontinuum s poluizračunljivim krajnjim točkama izračunljiv, te da je poluizračunljiva dvodimenzionalna ćelija s poluizračunljivim rubom izračunljiva. U četvrtom poglavlju definiramo nešto općenitiji ambijent, izračunljiv topološki prostor, i dokazujemo da je poluizračunljiv Hausdorffov kontinuum s poluizračunljivim krajnjim točkama izračunljiv u izračunljivom topološkom prostoru.

Abstract (english)

In this thesis we study computability of semicomputable sets in computable metric spaces. The thesis is divided into four chapters. In the first chapter we generalize theorems from classical computability theory to functions with values in \(\mathbb{Z}, \mathbb{Q}\) and \(\mathbb{R}\), and we prove some technical results which will be useful in further studies. In the second chapter we define computable metric spaces and we introduce some basic notions regarding computability in a metric space. We study computably enumerable, computable, semicomputable and co-computably enumerable sets. We show that a compact set in a computable metric space is computable if and only if it is semicomputable and computably enumerable. The main part of this thesis is the third chapter, in which we prove computability of certain semicomputable sets in a computable metric space. Namely, we prove that a semicomputable chainable continuum with semicomputable endpoints is computable, and that a semicomputable two-dimensional cell with semicomputable border is computable. In the fourth chapter we define a more general ambient space, computable topological space, and we show that a semicomputable Hausdorff continuum with semicomputable endpoints is computable in a computable topological space.

• Keywords: izračunljivost; metrički prostori; skupovi; Hausdorffov kontinuum
• Keywords (english): computability; metric spaces; sets; Hausdorff continuum
• Language: croatian
• URN:NBN: urn:nbn:hr:217:093776
• Study programme: Title: Pure Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-01-23 10:09:51