{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T04:30:45Z","timestamp":1772512245470,"version":"3.50.1"},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3479,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,9]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>We study reals with infinitely many incompressible prefixes. Call <jats:italic>A<\/jats:italic> \u2208 2<jats:sup><jats:italic>\u03c9<\/jats:italic><\/jats:sup><jats:italic>Kolmogorov random<\/jats:italic> if <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200007702_inline1\"\/>. where <jats:italic>C<\/jats:italic> denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by Martin-L\u00f6f. Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse\u2014proved by Nies. Stephan and Terwijn [11]\u2014this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.<\/jats:p>","DOI":"10.2178\/jsl\/1096901774","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T21:45:45Z","timestamp":1109799945000},"page":"907-913","source":"Crossref","is-referenced-by-count":17,"title":["Every 2-random real is Kolmogorov random"],"prefix":"10.1017","volume":"69","author":[{"given":"Joseph S.","family":"Miller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007702_ref015","unstructured":"Yu Liang , Decheng Ding , and Downey Rod G. , The Kolmogorov complexity of the random reals, submitted."},{"key":"S0022481200007702_ref014","unstructured":"Solovay Robert M. , Draft of paper (or series of papers) on Chaitin's work, unpublished notes. 215 pages, 05 1975."},{"key":"S0022481200007702_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694181"},{"key":"S0022481200007702_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF00534110"},{"key":"S0022481200007702_ref004","first-page":"3","article-title":"Three approaches to the definition of the concept \u201cquantity of information\u201d","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problemy Pereda\u010di Informacii"},{"key":"S0022481200007702_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"S0022481200007702_ref002","first-page":"113","volume-title":"Computational complexity (Courant Computer Science Symposium 7, New York University, New York, 1971)","author":"Daley","year":"1973"},{"key":"S0022481200007702_ref011","unstructured":"Nies Andr\u00e9 , Stephan Frank , and Terwijn Sebastiaan A. , Randomness, relativization and Turing degrees, submitted to this Journal."},{"key":"S0022481200007702_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S0022481200007702_ref010","unstructured":"Miller Joseph S. and Yu Liang , On initial segment complexity and degrees of randomness, in preparation."},{"key":"S0022481200007702_ref007","first-page":"61","volume-title":"ACM Symposium on the Theory of Computing (STOC)","author":"Loveland","year":"1969"},{"key":"S0022481200007702_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"S0022481200007702_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S0022481200007702_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"S0022481200007702_ref005","first-page":"548","article-title":"The concept of a random sequence","volume":"212","author":"Levin","year":"1973","journal-title":"Doklady Akademii Nauk SSSR"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007702","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T20:27:41Z","timestamp":1557174461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007702\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["S0022481200007702"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1096901774","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}