{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T02:45:26Z","timestamp":1777689926851,"version":"3.51.4"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":3571,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:title>Abstract.<\/jats:title><jats:p>Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-L\u00f6f randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-L\u00f6f randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-L\u00f6f random, and provide a new characterization of Schnorr random real numbers in terms of prefix-free machines. We prove that unlike Martin-L\u00f6f random c.e. reals, not all Schnorr random c.e. reals are Turing complete, though all are in high Turing degrees. We use the machine characterization to define a notion of \u201cSchnorr reducibility\u201d which allows us to calibrate the Schnorr complexity of reals. We define the class of \u201cSchnorr trivial\u201d reals, which are ones whose initial segment complexity is identical with the computable reals, and demonstrate that this class has non-computable members.<\/jats:p>","DOI":"10.2178\/jsl\/1082418542","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:37:48Z","timestamp":1109781468000},"page":"533-554","source":"Crossref","is-referenced-by-count":36,"title":["Schnorr randomness"],"prefix":"10.1017","volume":"69","author":[{"given":"Rodney G.","family":"Downey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evan J.","family":"Griffiths","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007891_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80030-3"},{"key":"S0022481200007891_ref014","unstructured":"Nies A. , Lowness properties and randomness, to appear."},{"key":"S0022481200007891_ref018","unstructured":"Solovay R. , Draft of paper (or series of papers) on Chaitin's work. Unpublished, 215 pages, 05 1975."},{"key":"S0022481200007891_ref003","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"S0022481200007891_ref002","first-page":"1","volume-title":"Complexity, logic and recursion theory","author":"Ambos-Spies","year":"1997"},{"key":"S0022481200007891_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0112458"},{"key":"S0022481200007891_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/257\/04023"},{"key":"S0022481200007891_ref006","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Problems of Information Transmission (Problemy Peredachi Informatsii)"},{"key":"S0022481200007891_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"},{"key":"S0022481200007891_ref020","unstructured":"Wang Y. , Randomness and complexity, Ph.D. thesis, University of Heidelberg, 1996."},{"key":"S0022481200007891_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0022481200007891_ref004","volume-title":"Mathematical Logic Quarterly","author":"Downey"},{"key":"S0022481200007891_ref010","first-page":"522","article-title":"Measures of complexity of finite objects (axiomatic description)","volume":"17","author":"Levin","year":"1976","journal-title":"Soviet Mathematics Doklady"},{"key":"S0022481200007891_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076224"},{"key":"S0022481200007891_ref005","first-page":"37","volume-title":"Computability and Complexity in Analysis","author":"Downey","year":"2002"},{"key":"S0022481200007891_ref008","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799357441"},{"key":"S0022481200007891_ref009","unstructured":"van Lambalgen M. , Random sequences, Ph.D. thesis, University of Amsterdam, 1987."},{"key":"S0022481200007891_ref013","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S0022481200007891_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90223-2"},{"key":"S0022481200007891_ref019","first-page":"1199","volume":"66","author":"Terwijn","year":"2001","journal-title":"Computational randomness and lowness"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007891","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T17:02:58Z","timestamp":1557162178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007891\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["S0022481200007891"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1082418542","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}