We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this property is referred to as punctually robust or P-TIME robust, respectively. We present both positive and negative results for structures corresponding to well-known representations of trees, such as binary trees, ordered trees, sequential (or prefix) trees, and partially ordered (poset) trees. A corollary of one of our results on trees is that semilattices and lattices are not punctually robust. In the main result of the paper, we demonstrate that, unlike Boolean algebras, modal algebras - that is, Boolean algebras with modality - are not punctually robust. The question of whether distributive lattices are punctually robust remains open. The paper contributes to a decades-old program on effective and feasible algebra, which has recently gained momentum due to rapid developments in punctual structure theory and its connections to online presentations of structures.

Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC 2021). In this model, there is no hypothesis fixed in advance; instead, Adversary—playing the role of Nature—can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.

Shapiro's notations for natural numbers, and the associated desideratum of acceptability - the property of a notation that all recursive functions are computable in it - is well-known in philosophy of computing. Computable structure theory, however, although capable of fully reconstructing Shapiro's approach, seems to be off philosophers' radar. Based on the case study of natural numbers with standard order, we make initial steps to reconcile these two perspectives. First, we lay the elementary conceptual groundwork for the reconstruction of Shapiro's approach in terms of computable structures and show, on a few examples, how results pertinent to the former can inform our understanding of the latter. Secondly, we prove a new result, inspired by Shapiro's notion of acceptability, but also relevant for computable structure theory. The result explores the relationship between the classical notion of degree spectrum of a computable function on the structure in question - specifically, having all c.e. degrees as a spectrum - and our ability to compute the (image of the) successor from the (image of the) function in any computable copy of the structure. The latter property may be otherwise seen as relativized acceptability of every notation for the structure.

Intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all computable isomorphic copies of that structure. We investigate the intrinsic complexity of unary total recursive functions on nonnegative integers with standard order. According to existing results, possible spectra of such functions include three sets consisting of precisely: the computable degree, all c.e. degrees and all $Δ_2$ degrees. These results, however, fall far short of the full classification. In this paper, we obtain a more complete picture by giving a few criteria for a function to have intrinsic complexity equal to one of the three candidate sets of degrees. Our investigations are based on the notion of block functions and a broader class of quasi-block functions beyond which all functions of interest have intrinsic complexity equal to the c.e. degrees. We also answer the questions raised by Wright and Harrison-Trainor by showing that the division between computable, c.e. and $Δ_2$ degrees is insufficient in this context as there is a unary total recursive function whose spectrum contains all c.e. degrees but is strictly contained in the $Δ_2$ degrees.

A novel kind of a negative result is presented for the problem of computable prediction. A non-stationary binary stochastic process is constructed for which almost surely no effective method of prediction achieves the infimum of prediction errors defined as the normalized Hamming distance between the sequence of predictions and the realization of the process. Yet it is shown that this process may be effectively predicted almost surely up to an arbitrarily small error since the infimum of prediction errors is zero.

Modulus of a computable approximation is a function which returns the number of a stage at which the approximation has already converged for its argument. The least modulus points at the earliest such stage for each of its arguments. We recall and show some properties of least moduli, including the ir close connection to c.e. degrees, and minimal witnessing functions for FM-representable sets. We observe, for instance, that the non-density theorem for the d.c.e. degrees gives an example of an incomplete degree that has no least moduli below 0_′. Using the properties of least moduli themselves, we construct a degree containing no least moduli for itself and having least moduli of incomparable degrees. In particular, the technique used demonstrates an approach of constructing a non-c.e. degree, which is somewhat different from that proposed by Cooper.