On initial segment complexity and degrees of randomness

One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define to mean that . The equivalence classes under this relation are the -degrees. We prove that if is -random, then and have no upper bound in the -degrees (hence, no join). We also prove that -randomness is closed upward in the -degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the -degrees. Unlike the -degrees, many basic properties of the -degrees are easy to prove. We show that implies , so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for , the analogue of for plain Kolmogorov complexity.

Two other interesting results are included. First, we prove that for any , a -random real computable from a --random real is automatically --random. Second, we give a plain Kolmogorov complexity characterization of -randomness. This characterization is related to our proof that implies .