On initial segment complexity and degrees of randomness

Abstract

One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define $X\leq _K Y$ to mean that $(\forall n)\; K(X\upharpoonright n)\leq K(Y\upharpoonright n)+O(1)$. The equivalence classes under this relation are the $K$-degrees. We prove that if $X\oplus Y$ is $1$-random, then $X$ and $Y$ have no upper bound in the $K$-degrees (hence, no join). We also prove that $n$-randomness is closed upward in the $K$-degrees. Our main tool is another structure intended to measure the degree of randomness of real numbers: the $\textit {vL}$-degrees. Unlike the $K$-degrees, many basic properties of the $\textit {vL}$-degrees are easy to prove. We show that $X\leq _K Y$ implies $X\leq _{\textit {vL}} Y$, so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for $\leq _C$, the analogue of $\leq _K$ for plain Kolmogorov complexity. Two other interesting results are included. First, we prove that for any $Z\in 2^\omega$, a $1$-random real computable from a $1$-$Z$-random real is automatically $1$-$Z$-random. Second, we give a plain Kolmogorov complexity characterization of $1$-randomness. This characterization is related to our proof that $X\leq _C Y$ implies $X\leq _{\textit {vL}} Y$.