id: 05288807
dt: j
an: 05288807
au: Miller, Joseph S.; Yu, Liang
ti: On initial segment complexity and degrees of randomness.
so: Trans. Am. Math. Soc. 360, No. 6, 3193-3210 (2008).
py: 2008
pu: American Mathematical Society, Providence, RI
la: EN
cc: 
ut: initial segment complexity; plain Kolmogorov complexity
ci: 
li: doi:10.1090/S0002-9947-08-04395-X
ab: Summary: 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 $
    {vL}$-degrees. Unlike the $ K$-degrees, many basic properties of the $
    {vL}$-degrees are easy to prove. We show that $ X\leq_K Y$ implies $
    X\leq_{{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^ω$, 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_{{vL}} Y$.
rv: