Topološki aspekti izračunljivosti

master's thesis

• Author: Lucija Validžić
• Mentor: Zvonko Iljazović (mentor)
• Committee member: Zvonko Iljazović (predsjednik povjerenstva)
• Committee member: Dražen Adamović (član povjerenstva)
• Committee member: Ljiljana Arambašić (član povjerenstva)
• Committee member: Damir Bakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2016-09-27, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Rad je logički podjeljen u tri poglavlja. Prvo poglavlje je općenito o izračunljivosti i predstavlja temelj za daljnja razmatranja. U drugom poglavlju bavimo se izračunljivim metričkim prostorima. Kako bismo uveli teoriju izračunljivosti u metrički prostor, govorimo o izračunljivim točkama, izračunljivim nizovima, izračunljivim skupovima, izračunljivo prebrojivim skupovima, poluizračunljivim skupovima. Dokazujemo da ako je potpun skup S izračunljiv u točki, tada možemo pronaći izračunljivu okolinu u S te točke proizvoljno malog dijametra. Posljedica ovoga i rezultata iz [5] je da su izračunljive točke guste u poluizračunljivim mnogostrukostima i poluizračunljivim topološkim poliedrima. Treće poglavlje je o izračunljivim topološkim prostorima. Slično kao u prethodnom poglavlju, definiramo osnovne pojmove koji su nam važni za uvođenje izračunljivosti u topološke prostore i bavimo se uvjetima uz koje su poluizračunljivi lančasti i poluizračunljivi cirkularno lančasti kontinuumi izračunljivi. Dokazujemo da ako je Hausdorffov kontinuum poluizračunljiv i lančast od a do b, gdje su a i b izračunljive točke, tada je nužno i izračunljiv. Osim toga, pokazujemo da poluizračunljivost Hausdorffovog kontinuuma koji je cirkularno lančast, ali ne i lančast, povlači njegovu izračunljivost.

Abstract (english)

This thesis is logically divided into three chapters. First chapter is generally about computability and it forms a basis for further studies. In the second chapter we talk about computable metric spaces. In order to introduce computability into metric spaces, we define computable points, computable sequences, computable sets, computably enumerable sets, semicomputable sets. We prove that if a semicomputable set S is computable in a point, then we can find a computable neighbourhood of that point in S which has arbitrarily small diameter. As a consequence of that and results from [5], we get that computable points are dense in semicomputable manifolds and semicomputable topological polyhedra. The last chapter is about computable topological spaces. Similarly as in previous chapter, we introduce notions which we use to establish some connections between the computability theory and topology. We investigate sufficient conditions under which semicomputable chainable and circularly chainable continua are computable. We show that if a Hausdorff continuum is semicomputable and chainable from a to b, where a and b are computable points, then it is computable. Moreover, we prove that semicomputability of a Hausdorff continuum which is circularly chainable, but not chainable, implies its computability

• Keywords: izračunljivi metrički prostori; izračunljivi topološki prostori; poluizračunljivi lančasti kontinuumi; poluizračunljivi cirkularno lančasti kontinuumi; Hausdorffov kontinuum
• Keywords (english): computable metric spaces; computable topological spaces; semicomputable chainable continua; circularly chainable continua; Hausdorff continuum
• Language: croatian
• URN:NBN: urn:nbn:hr:217:453547
• 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: 2019-02-18 13:17:06