Maksimalne strukture izračunljivosti

diplomski rad

• Naslov (engleski): Maximum computability structures
• Autor: Ana Krmpotić
• Mentor: Zvonko Iljazović (mentor)
• Član povjerenstva: Zvonko Iljazović (predsjednik povjerenstva)
• Član povjerenstva: Marko Horvat (član povjerenstva)
• Član povjerenstva: Mladen Vuković (član povjerenstva)
• Član povjerenstva: Vedran Čač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: 2020-09-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Ovaj diplomski rad podijeljen je u tri poglavlja. U prvom poglavlju govorimo o klasičnoj izračunljivosti i generaliziranju pojma rekurzivne funkcije na funkcije s vrijednostima u \(\mathbb{Z}\) i \(\mathbb{Q}\). U drugom poglavlju govorimo o rekurzivno prebrojivim skupovima, izračunljivim brojevima i rekurzivnim funkcijama s kodomenom \(\mathbb{R}\). Dajemo karakterizacije izračunljivih brojeva i primjer neizračunljivog broja koji je limes rekurzivnog niza. Nadalje, definiramo rekurzivne funkcije s vrijednostima u \(\mathbb{R}\) i generaliziramo tvrdnje iz prvog poglavlja, ali i dajemo protuprimjere za tvrdnje koje ne vrijede proširenjem kodomene. Tako pokazujemo da skup nultočaka rekurzivne funkcije s vrijednostima u \(\mathbb{R}\) ne mora biti rekurzivan, niti rekurzivno prebrojiv. U trećem poglavlju govorimo o pojmu izračunljivosti u metričkim prostorima. Dajemo definiciju i primjere izračunljivih metričkih prostora te rezultate koji će biti osnova za uvodenje struktura izračunljivosti na metričke prostore. Zatim proučavamo strukture izračunljivosti i dajemo definicije separabilnih i maksimalnih struktura izračunljivosti. Dokazujemo da je svaka struktura izračunljivosti sadržana u nekoj maksimalnoj te da su maksimalne strukture izračunljivosti na euklidskom prostoru separabilne. Nadalje, pokazujemo da na [0; 1] postoji jedinstvena separabilna struktura izračunljivosti.

Sažetak (engleski)

This thesis is divided into three chapters. In the first chapter we talk about classical computability theory and generalizing the definition of a recursive function to functions with values in \(\mathbb{Z}\) and \(\mathbb{Q}\). In the second chapter we talk about recursively enumerable sets, computable numbers and recursive functions with the codomain \(\mathbb{R}\). We give two characterizations of computable numbers and an example of a non-computable number which is a limit of a recursive sequence. Furthermore, we define recursive functions with values in \(\mathbb{R}\) and generalize results from the first chapter, but also give counterexamples for claims that do not hold by expanding the codomain. That way we show that the set of roots of a recursive function with values in \(\mathbb{R}\) is not necessarily recursive, or even recursively enumerable. In the third chapter we talk about computability in metric spaces. We give the definition and examples of computable metric spaces with results that will serve as a motivation for introducing computability structures on metric spaces. Then we study computability structures and give definitions of separable and maximal computability structures. We prove that every computability structure is a subset of some maximal computability structure and also that every maximal computability structure on Euclidean space is separable. Moreover, we prove that there exists a unique separable computability structure on [0; 1].

• Ključne riječi: klasična izračunljivost; rekurzivna funkcija; neizračunljiv broja
• Ključne riječi (engleski): classical computability; recursive function; non-computable number
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:691795
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-02-26 12:54:33