On initial segment complexity and degrees of randomness
By Joseph S. Miller, Liang Yu. 2008
89 citations recorded by the source corpus.
One approach to understanding the fine structure of initial segment complexity was introduced by Downey, Hirschfeldt and LaForte. They define X ≤K Y to mean that (Vn) K(X | n) < K(Y | n) + 0(1). The equivalence classes under this relation are the K-degrees. We prove that if X ⊕ 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 ≤K Y implies X ≤vL Y, so some results can be transferred. The reverse implication is proved to fail. The same analysis is also done for ≤c, the analogue of ≤K for plain Kolmogorov complexity. Two other interesting results are included. First, we prove that for any Z ∈ 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 ≤C Y implies X ≤vL Y.
Subfields: Computational Theory and Mathematics, Statistics and Probability
View Paper: https://www.semanticscholar.org/paper/dc8cd09f7ebd5bbcfdcc4ef42fe80f5eb9926aaa
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Statistics and Probability
Citations in the corpus
- Computability and randomness (2009, background): “8 due to Mohrherr (1984), if E is a set such that ∅′ ≤tt E, then X ≤wtt E implies X ≤tt E.”