The K-Degrees, Low for K Degrees,and Weakly Low for K Sets
Miller , Joseph S.
Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, p. 381-391 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is infinitely often maximal. This had previously been proved for plain Kolmogorov complexity.
Publié le : 2009-10-15
Classification:  Martin-Lof randomness,  prefix-free Kolmogorov complexity,  68Q30,  03D30,  03D80 
@article{1265899121,
     author = {Miller ,  Joseph S.},
     title = {The K-Degrees, Low for K Degrees,and Weakly Low for K Sets},
     journal = {Notre Dame J. Formal Logic},
     volume = {50},
     number = {1},
     year = {2009},
     pages = { 381-391},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1265899121}
}

Miller ,  Joseph S. The K-Degrees, Low for K Degrees,and Weakly Low for K Sets. Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, pp.  381-391. http://gdmltest.u-ga.fr/item/1265899121/