Topološki prostori izračunljivog tipa

diplomski rad

• Autor: Matea Čelar
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Vedran Čačić (član povjerenstva)
• Član povjerenstva: Slaven Kožić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2019-09-20, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: izračunljivost; metrički prostori; skupovi; Hausdorffov kontinuum
• Ključne riječi (engleski): computability; metric spaces; sets; Hausdorff continuum
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:093776
• Studijski program: Naziv: Teorijska matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-01-23 10:09:51