Randomness, relativization and Turing degrees

Abstract. We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Lof random relative to;(n1). We show that a set is 2-random if and only if there is a constant c such that innitely many initial segments x of the set are c-incompressible: C(x) jxj c. The `only if ' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Lof randomness, recursive random-ness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. Mathematical Subject Classification: 68Q30, 03D15, 03D28, 03D80, 28E15. 1