{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T03:14:39Z","timestamp":1778901279333,"version":"3.51.4"},"reference-count":85,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"unspecified","delay-in-days":369,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Bull. symb. log"],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.<\/jats:p>","DOI":"10.1017\/s1079898600010672","type":"journal-article","created":{"date-parts":[[2016,7,28]],"date-time":"2016-07-28T04:31:15Z","timestamp":1469680275000},"page":"318-350","source":"Crossref","is-referenced-by-count":3,"title":["Algorithmic Randomness and Measures of Complexity"],"prefix":"10.1017","volume":"19","author":[{"given":"George","family":"Barmpalias","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"S1079898600010672_ref072","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.006"},{"key":"S1079898600010672_ref010","unstructured":"Barmpalias George and Downey Rodney G. , Exact pairs for the ideal of the K- trivial sequences in the Turing degrees, preprint, 2012."},{"key":"S1079898600010672_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-09-04910-1"},{"key":"S1079898600010672_ref048","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdm041"},{"key":"S1079898600010672_ref009","unstructured":"Barmpalias George , Universal computably enumerable sets and initial segment prefix-free complexity, Information and Computation , in press."},{"key":"S1079898600010672_ref062","first-page":"548","article-title":"The concept of a random sequence","volume":"212","author":"Levin","year":"1973","journal-title":"Doklady Akademii Nauk. SSSR"},{"key":"S1079898600010672_ref049","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_34"},{"key":"S1079898600010672_ref077","first-page":"215","volume-title":"Hierarchies of randomness tests","author":"Reimann"},{"key":"S1079898600010672_ref082","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"S1079898600010672_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0012-5"},{"key":"S1079898600010672_ref046","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80004-3"},{"key":"S1079898600010672_ref041","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.01.002"},{"key":"S1079898600010672_ref008","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.06.008"},{"key":"S1079898600010672_ref063","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S1079898600010672_ref055","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":"S1079898600010672_ref050","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.40.605"},{"key":"S1079898600010672_ref057","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799357441"},{"key":"S1079898600010672_ref005","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2010-012"},{"key":"S1079898600010672_ref029","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00159-0"},{"key":"S1079898600010672_ref036","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/j.apal.2004.01.006","article-title":"The Kolmogorov complexity of random reals","volume":"129","author":"Ding","year":"2004","journal-title":"Annals of Pure and Applied Logic"},{"key":"S1079898600010672_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90005-0"},{"key":"S1079898600010672_ref018","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1264433928"},{"key":"S1079898600010672_ref060","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670130102"},{"key":"S1079898600010672_ref045","first-page":"244","article-title":"Some properties of sw-reducibility","volume":"22","author":"Fan","year":"2005","journal-title":"Nanjing University. Journal. Mathematical Biquarterly"},{"key":"S1079898600010672_ref067","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2009-017"},{"key":"S1079898600010672_ref026","first-page":"147","volume-title":"Symposium on Theoretical Aspects of Computer Science 2009","author":"Bienvenu","year":"2009"},{"key":"S1079898600010672_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.01.007"},{"key":"S1079898600010672_ref052","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2011-05306-7"},{"key":"S1079898600010672_ref073","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"S1079898600010672_ref074","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1120224726"},{"key":"S1079898600010672_ref056","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076224"},{"key":"S1079898600010672_ref007","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exq036"},{"key":"S1079898600010672_ref053","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/jdr072"},{"key":"S1079898600010672_ref035","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.10.001"},{"key":"S1079898600010672_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.11.004"},{"key":"S1079898600010672_ref033","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2010.06.008"},{"key":"S1079898600010672_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2008.06.004"},{"key":"S1079898600010672_ref042","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376937"},{"key":"S1079898600010672_ref034","unstructured":"Day Adam R. and Miller Joseph S. , private communication, 08 2012."},{"key":"S1079898600010672_ref078","doi-asserted-by":"publisher","DOI":"10.2307\/1970214"},{"key":"S1079898600010672_ref021","unstructured":"Barmpalias George and Li Angsheng , Kolmogorov complexity and computably enumerable sets, Annals of Pure and Applied Logic , (in press)."},{"key":"S1079898600010672_ref071","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00028-7"},{"key":"S1079898600010672_ref059","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794268789"},{"key":"S1079898600010672_ref061","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1999.2794"},{"key":"S1079898600010672_ref037","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.2178\/jsl\/1102022216","article-title":"There is no sw-complete c.e. real","volume":"69","author":"Ding","year":"2004","journal-title":"The Journal of Symbolic Logic"},{"key":"S1079898600010672_ref003","first-page":"8","volume-title":"Computability in Europe","volume":"3526","author":"Barmpalias","year":"2005"},{"key":"S1079898600010672_ref038","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68441-3"},{"key":"S1079898600010672_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9400-9"},{"key":"S1079898600010672_ref054","doi-asserted-by":"publisher","DOI":"10.2307\/1969708"},{"key":"S1079898600010672_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.06.006"},{"key":"S1079898600010672_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2010.12.005"},{"key":"S1079898600010672_ref047","doi-asserted-by":"crossref","DOI":"10.1142\/9789812772749","volume-title":"Proceedings of the 9th Asian logic conference","author":"Goncharov","year":"2006"},{"key":"S1079898600010672_ref068","first-page":"390","volume":"12","author":"Miller","year":"2006","journal-title":"Randomness and computability: open questions"},{"key":"S1079898600010672_ref015","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1017\/S0960129506005445","article-title":"Random reals and Lipschitz continuity","volume":"16","author":"Barmpalias","year":"2006","journal-title":"Mathematical Structures in Computer Science"},{"key":"S1079898600010672_ref028","unstructured":"Bienvenu Laurent , Miller Joseph S. , H\u00f6lzl Rupert , and Nies Andr\u00e9 , Denjoy, Demuth and density, in preparation, 2012."},{"key":"S1079898600010672_ref065","first-page":"60","volume-title":"IEEE Conference on Computational Complexity, 2007","author":"Merkle","year":"2007"},{"key":"S1079898600010672_ref081","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S1079898600010672_ref064","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S1079898600010672_ref051","first-page":"149","volume-title":"Symposium on theoretical aspects of computer science","author":"Kjos-Hanssen","year":"2006"},{"key":"S1079898600010672_ref084","unstructured":"Sterkenburg Tom , Sequences with trivial initial segment complexity, MSc dissertation, University of Amsterdam, 02 2011."},{"key":"S1079898600010672_ref079","doi-asserted-by":"publisher","DOI":"10.2307\/1970393"},{"key":"S1079898600010672_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9424-1"},{"key":"S1079898600010672_ref006","first-page":"609","volume":"5","author":"Barmpalias","year":"2011","journal-title":"International Journal of Software and Informatics"},{"key":"S1079898600010672_ref040","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44683-4_28"},{"key":"S1079898600010672_ref039","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.07.004"},{"key":"S1079898600010672_ref070","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2010.12.022"},{"key":"S1079898600010672_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.10.001"},{"key":"S1079898600010672_ref013","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1153858646"},{"key":"S1079898600010672_ref075","volume-title":"Classical recursion theory","volume":"I","author":"Odifreddi","year":"1989"},{"key":"S1079898600010672_ref017","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2011.0031"},{"key":"S1079898600010672_ref066","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1096901774"},{"key":"S1079898600010672_ref058","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1243948325"},{"key":"S1079898600010672_ref019","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1208359060"},{"key":"S1079898600010672_ref080","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44683-4"},{"key":"S1079898600010672_ref043","doi-asserted-by":"publisher","DOI":"10.1142\/9789812705815_0005"},{"key":"S1079898600010672_ref069","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-08-04395-X"},{"key":"S1079898600010672_ref016","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1016\/j.apal.2006.08.001","article-title":"Randomness and the linear degrees of computability","volume":"145","author":"Barmpalias","year":"2007","journal-title":"Annals of Pure and Applied Logic"},{"key":"S1079898600010672_ref030","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"S1079898600010672_ref032","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-05-08086-X"},{"key":"S1079898600010672_ref076","doi-asserted-by":"crossref","unstructured":"Raichev Alexander and Stephan Frank , A minimal rK-degree, In Goncharov et al. [47], pp. 261\u2013270.","DOI":"10.1142\/9789812796554_0014"},{"key":"S1079898600010672_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.09.020"},{"key":"S1079898600010672_ref085","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-45.1.161"},{"key":"S1079898600010672_ref083","unstructured":"Solovay R. , Handwritten manuscript related to Chaitin's work, 1975, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 215 pages."},{"key":"S1079898600010672_ref027","first-page":"452","volume-title":"Symposium on Theoretical Aspects of Computer Science 2011","author":"Bienvenu","year":"2011"},{"key":"S1079898600010672_ref044","first-page":"411","volume":"12","author":"Downey","year":"2006","journal-title":"Calibrating randomness"}],"container-title":["The Bulletin of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1079898600010672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T16:15:15Z","timestamp":1556036115000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1079898600010672\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":85,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S1079898600010672"],"URL":"https:\/\/doi.org\/10.1017\/s1079898600010672","relation":{},"ISSN":["1079-8986","1943-5894"],"issn-type":[{"value":"1079-8986","type":"print"},{"value":"1943-5894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}