Arriving on Time: Punctuality in Structures, Isomorphisms and 1-Decidability

This thesis contributes to the area of computable structure theory. In particular, it contributes to the study of punctual structures; the systematic study of the primitive recursive content of mathematics initiated by Kalimullin, Melnikov and Ng in [KMN17]. We investigate of finite punctual dimension, the punctual degrees (a degree structure induced by primitive recursive isomorphisms) and punctual 1-decidability. We show that the simple trick in order to show there exists structure of finite computable dimension n > 2 does not work in the punctual case and therefore we give a construction of structure of finite punctual dimension n > 2 by hand which uses the techniques of the construction of a structure of punctual dimension 2 in [MN20]. We explore embedding lattices in the punctual degrees of various linear orders, by embedding the atomless Boolean algebra while preserving supremums and infimums. Finally we investigate punctual 1-decidability, including classifying 1-decidable Boolean algebra with computable isomorphisms to punctually 1-decidable presentations and showing that there is a structure that is punctually 1-decidably categorical but not 1-decidably categorical; the 1-decidable analogue of the surprising result from [KMN17]. The thesis highlights that new techniques are required once we forbid unbounded search and studying punctual structures allows us to understand the nature of the use of unbounded search in computable structure theory.