| Sumario: | We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is MartinLöf random relative to &0slash;(). 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) ≥ ¦x¦ - c. The ‘only if’ direction was obtained independently by Joseph Miller. This characterization can be extended to the cast: 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 MartinLöf randomness, recursive randomness, 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.
|
|---|