`Contributions to ceers, logical depth, algorithmic randomness and their applications

This thesis collects some contributions to different fields of computability theory and algorithmic randomness. The first line of research, on which I have worked jointly with Luca San Mauro and Andrea Sorbi, concerns computable reducibility on the equivalence relations on the set of natural numbers. Extending Ershov's category-theoretic approach, we have investigated various properties of the category of equivalence relations on the natural numbers, where the morphisms from an equivalence relation R to another equivalence relation S are those maps from R-equivalence classes to S-equivalence classes, which are induced by computable functions. We have also studied some important full subcategories, such that the ones of c.e.~equivalence relations, which we often referred to simply as ceers, and of co-c.e.~relations. Moreover, we have studied the ``expressiveness'' of certain classes of effectively presented algebraic structures using the tools of computable reducibility: namely, we have studied which ceers lie in the same degree (with respect to the degree structure induced by computable reducibility) of the word problem of some member of various classes of familiar algebraic structures, such as semigroups, groups and rings. Our main result, which answers an open question in the literature, is that, while in every degree there is the word problem of some c.e. semigroup, there are ceers which are not bi-reducible to the word problem of any finitely generated semigroup: in fact, it is even possible to identify a natural computability-theoretic property (which we have called hyperdarkness) preventing ceers from being in the same degree of the word problem of any finitely generated semigroup. The second project, joint with Laurent Bienvenu and Wolfgang Merkle, focuses on logical depth. This notion has been introduced by Bennett and aims to capture the intuitive idea of the internal organization of information. In particular, we have studied how depth relativizes to various classes of oracles, in order to better understand which oracles do actually help in organizing information: the main results are that the class of deep sequences with respect to the halting set is incomparable (with respect to the inclusion) with the corresponding unrelativized class, while the class of deep sets relative to any Martin-Löf random sequence strictly contains the unrelativized one. A consequence of our results is that we slightly strengthen a result in the literature, stating that every PA-complete degree is the join of two ML-random degrees: in fact, we show that every DNC 2-valued function is truth-table-equivalent to the join of two Martin-Löf random sets. Finally, in the last project, which is joint work with Laurent Bienvenu and Tomasz Steifer, we have compared deterministic forecasting schemes against probabilistic ones, using the toolkit of algorithmic randomness and, in particular, the notion of martingales. We have introduced a new notion in the ``randomness zoo'': we call a sequence X almost everywhere computably random if, for almost every sequence Y (i.e. up to a null class) X is computably random relatively to Y. Notice that this approach is indeed equivalent to consider probabilistically computable martingales, by simply assuming that Y has been drawn at random in advance. Then, using the so-called fireworks technique, we have built a partial computable sequence (roughly speaking, a sequence on which no deterministic martingale succeeds) which is not almost everywhere computably random, hence proving that probabilistic martingales are actually stronger than deterministic ones. It is worth noticing that this is a quite unusual result in computability theory, starkly contrasting the classical result that the sequences which can be computed by some probabilistic algorithm with positive probability coincide with the deterministically computable ones.