{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:43Z","timestamp":1777596163198,"version":"3.51.4"},"reference-count":24,"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 present a comparatively simple way to construct Martin-L\u00f6f random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of G\u00e1cs and Ku\u010dera, for any given set <jats:italic>X<\/jats:italic> we construct a Martin-L\u00f6f random set from which <jats:italic>X<\/jats:italic> can be decoded effectively.<\/jats:p><jats:p>By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-L\u00f6f random sets that are computably enumerable self-reducible. The two latter results complement the known facts that no rec-random set is truth-table autoreducible and that no Martin-L\u00f6f random set is Turing-autoreducible [8, 24].<\/jats:p>","DOI":"10.2178\/jsl\/1096901772","type":"journal-article","created":{"date-parts":[[2005,3,2]],"date-time":"2005-03-02T16:45:04Z","timestamp":1109781904000},"page":"862-878","source":"Crossref","is-referenced-by-count":13,"title":["On the construction of effectively random sets"],"prefix":"10.1017","volume":"69","author":[{"given":"Wolfgang","family":"Merkle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nenad","family":"Mihailovi\u0107","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200007684_ref024","first-page":"814","article-title":"On autoreducibility","volume":"11","author":"Trakhtenbrot","year":"1970","journal-title":"Soviet Mathematics Doklady"},{"key":"S0022481200007684_ref019","volume-title":"Classical Recursion Theory","author":"Odifreddi","year":"1989"},{"key":"S0022481200007684_ref017","unstructured":"Mayordomo E. , Contributions to the study of resource-hounded measure, Ph.D. thesis , Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain, 1994."},{"key":"S0022481200007684_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"S0022481200007684_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"S0022481200007684_ref012","first-page":"219","volume-title":"Logic Colloquium'87","volume":"129","author":"Ku\u010dera","year":"1989"},{"key":"S0022481200007684_ref008","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415317"},{"key":"S0022481200007684_ref007","unstructured":"Ebert T. , Applications of recursive operators to randomness and complexity, Ph.D. thesis , University of California at Santa Barbara, 1998."},{"key":"S0022481200007684_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04978-5"},{"key":"S0022481200007684_ref004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-79235-9"},{"key":"S0022481200007684_ref001","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/257\/04023"},{"key":"S0022481200007684_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00027-5"},{"key":"S0022481200007684_ref021","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0112458"},{"key":"S0022481200007684_ref010","first-page":"1226","article-title":"Surjective functions on computably growing Cantor sets","volume":"3","author":"Hertling","year":"1996","journal-title":"Journal of Universal Computer Science"},{"key":"S0022481200007684_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076224"},{"key":"S0022481200007684_ref003","volume-title":"Mathematical Analysis","author":"Apostol","year":"1978"},{"key":"S0022481200007684_ref023","unstructured":"Terwijn S. A. , Computability and measure, Ph.D. thesis , Universiteit van Amsterdam, Amsterdam, Netherlands, 1998."},{"key":"S0022481200007684_ref002","first-page":"1","volume-title":"Complexity, Logic, and Recursion Theory","author":"Ambos-Spies","year":"1997"},{"key":"S0022481200007684_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"S0022481200007684_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"},{"key":"S0022481200007684_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694181"},{"key":"S0022481200007684_ref018","first-page":"230","volume-title":"Proceedings of the IEEE Conference on Computational Complexity","author":"Merkle","year":"2003"},{"key":"S0022481200007684_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80004-3"},{"key":"S0022481200007684_ref022","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200007684","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T16:27:11Z","timestamp":1557160031000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200007684\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,9]]}},"alternative-id":["S0022481200007684"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1096901772","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,9]]}}}