Every 2-random real is Kolmogorov random

Miller, Joseph S.

J. Symbolic Logic, Tome 69 (2004) no. 1, p. 907-913 / Harvested from Project Euclid

Résumé

We study reals with infinitely many incompressible prefixes. Call A∈ 2^ω Kolmogorov random if (∃^∞n) C(A↾ n)> n-(1), where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by Martin-Löf, Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse—proved by Nies, Stephan and Terwijn [NST]—this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.

Publié le : 2004-09-14
Classification:

@article{1096901774,
     author = {Miller, Joseph S.},
     title = {Every 2-random real is Kolmogorov random},
     journal = {J. Symbolic Logic},
     volume = {69},
     number = {1},
     year = {2004},
     pages = { 907-913},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1096901774}
}

Miller, Joseph S. Every 2-random real is Kolmogorov random. J. Symbolic Logic, Tome 69 (2004) no. 1, pp.  907-913. http://gdmltest.u-ga.fr/item/1096901774/