We investigate the problem of punctual (fully primitive recursive) presentability of algebraic structures up to primitive recursive and computable isomorphism. We show that for mono-unary structures and undirected graphs, if a structure is not punctually categorical then it has infinitely many punctually non-isomorphic punctual presentations. We also show that the punctual degrees of any computably almost rigid structure as well as the order ($$\mathbb {Z},<$$ Z, < ) are dense. Finally we characterise the Boolean algebras which have a punctually 1-decidable (...) presentation that is computably isomorphic to a 1-decidable presentation. (shrink)

Several papers (e.g. [7, 23, 42]) have recently sought to give general frameworks for online structures and algorithms ([4]), and seeking to connect, if only by analogy, online and computable structure theory. These initiatives build on earlier work on online colouring and other combinatorial algorithms by Bean [10], Kierstead, Trotter et al. [48, 54, 57] and others, as we discuss below. In this paper we will look at such frameworks and illustrate them with examples from the first author’s MSc Thesis (...) ([58]). In this thesis, Askes looks at online, adversarial online and strongly online algorithms and structures. Additionally, we prove some new theorems about online algorithms on graphs of bounded pathwidth as well as some new results on punctually 1-decidable structures. (shrink)