We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on reducibilities that measure the initial segment complexity of reals and the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.

A completely mitotic computably enumerable degree is a c.e. degree in which every c.e. set is mitotic, or equivalently in which every c.e. set is autoreducible. There are known to be low, low2, and high completely mitotic degrees, though the degrees containing non-mitotic sets are dense in the c.e. degrees. We show that there exists an upper cone of c.e. degrees each of which contains a non-mitotic set, and that the completely mitotic c.e. degrees are nowhere dense in the c.e. (...) degrees. We also show that there is a set computably enumerable in and above 0′ which is not the jump of any completely mitotic degree. (shrink)

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of (...) r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP. (shrink)