On initial segment complexity and degrees of randomness
Joseph S. Miller, Liang Yu · Transactions of the American Mathematical Society · 2008
One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define X ≤ K Y X\leq _K Y to mean that ( ∀ n ) K ( X ↾ n ) ≤ K ( Y ↾ n ) + O ( 1 ) (\forall n)\; K(X\upharpoonright n)\leq K(Y\upharpoonright n)+O(1) . The equivalence classes under this relation are the K K -degrees . We prove that if X ⊕ Y X\oplus Y is 1 1 -random, then X X and Y Y have no upper bound in the K K -degrees (hence, no join). We also prove that n n -randomness is closed upward in the K K -degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the vL \textit {vL} -degrees. Unlike the K K -degrees, many basic properties of the vL \textit {vL} -degrees are easy to prove. We show that