Randomness, relativization, and Turing degrees

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 . We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) c. The `only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity