Praca licencjacka
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Syntactic characterisation of intrinsic computability

Uproszczony widok
dc.abstract.enComputable structure theory considers the question how computational properties of computable structures differ between their isomorphic copies. In this thesis I consider the notions of intrinsic computability and intrinsic computable enumerability which occupy a key position in computable structure theory. These notions refer to relations which are computable (or computably enumerable) in every computable copy of a structure. I present some examples of instrinsically computable relations. I also present proofs of theorems which establish connection between intrinsic computability and other important notions of computable structure theory such as computable stability and computable categoricity. The main result of this paper is the detailed reconstruction of Ash-Nerode theorem establishing connection between intrinsic computable enumerability (and intrinsic computability) and definitability by a certain class of infinitary formulas in $\mathcal{L}_{\omega_{1},\omega}$ logic (under an effectiveness condition). I show certain applications of this theorem, in particular to vector spaces.
dc.abstract.plTeoria struktur obliczalnych rozważa pytanie, jak własności obliczalne struktur obliczalnych różnią się w ich kopiach obliczalnych. W tej rozprawie rozważam pojęcie wewnętrznej obliczalności i wewnętrznej rekurencyjnej przeliczalności, które zajmują kluczową pozycję w teorii struktur obliczalnych. Te pojęcia dotyczą relacji, które są obliczalne (albo rekurencyjnie przeliczalne) w każdej obliczalnej kopii struktury. Prezentuję przykłady relacji wewnętrznie obliczalnych. Prezentuję również dowody twierdzeń ukazujących zależność między wewnętrzną obliczalnością a innymi ważnymi pojęciami z zakresu teorii struktur obliczalnych, takimi jak obliczalna stabilność i obliczalna kategoryczność. Głównym rezultatem tej pracy jest rekonstrukcja twierdzenia Asha-Nerode'a ukazującego rozbieżność między wewnętrzną rekurencyjną przeliczalnością a definiowalnością za pomocą pewnej klasy nieskończonych formuł w logice infinitarnej (przy założeniu warunku efektywności). Pokazuję pewne zastosowania tego twierdzenia, w szczególności do przestrzeni liniowych.
dc.affiliationUniwersytet Warszawski
dc.affiliation.departmentWydział Filozofii
dc.contributor.authorDaca, Herbert
dc.date.accessioned2025-01-09T12:42:29Z
dc.date.available2025-01-09T12:42:29Z
dc.date.defence2023-12-21
dc.date.issued2023
dc.date.submitted2023-12-07
dc.description.promoterWrocławski, Michał
dc.description.reviewerWrocławski, Michał
dc.description.reviewerKalociński, Dariusz
dc.identifier.apd228782
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/161839
dc.languageen
dc.language.otherpl
dc.publisherUniwersytet Warszawski
dc.rightsClosedAccess
dc.subject.enintrinsic computability
dc.subject.enAsh-Nerode theorem
dc.subject.encomputable structure
dc.subject.eninfinitary logic
dc.subject.encomputable vector space
dc.subject.plwewnętrzna obliczalność
dc.subject.pltwierdzenie Asha-Nerdoe'a
dc.subject.plobliczalna struktura
dc.subject.plinfinitarna logika
dc.subject.plobliczalna przestrzeń liniowa
dc.titleSyntactic characterisation of intrinsic computability
dc.title.alternativeSyntaktyczna charakteryzacja wewnętrznej obliczalności
dc.typeBachelorThesis
dspace.entity.typePublication