Characterizing Lowness For Demuth Randomness

Bienvenu, Laurent; Downey, Rod; Greenberg, Noam; Nies, Andre; Turetsky, Dan

dc.contributor.author	Bienvenu, Laurent	en
dc.contributor.author	Downey, Rod	en
dc.contributor.author	Greenberg, Noam	en
dc.contributor.author	Nies, Andre	en
dc.contributor.author	Turetsky, Dan	en
dc.date.accessioned	2015-01-28T00:11:49Z	en
dc.date.issued	2014-06	en
dc.identifier.citation	Journal of Symbolic Logic, 2014, 79 (02), pp. 526 - 560	en
dc.identifier.issn	0022-4812	en
dc.identifier.uri	http://hdl.handle.net/2292/24275	en
dc.description.abstract	We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.	en
dc.publisher	Association for Symbolic Logic	en
dc.relation.ispartofseries	Journal of Symbolic Logic	en
dc.rights	Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. Details obtained from http://journals.cambridge.org/images/fileUpload/images/JSL_CTF.zip http://www.sherpa.ac.uk/romeo/issn/0022-4812/	en
dc.rights.uri	https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm	en
dc.title	Characterizing Lowness For Demuth Randomness	en
dc.type	Journal Article	en
dc.identifier.doi	10.1017/jsl.2013.21	en
pubs.issue	02	en
pubs.begin-page	526	en
pubs.volume	79	en
dc.description.version	VoR - Version of Record	en
dc.rights.holder	Copyright: Association for Symbolic Logic	en
pubs.end-page	560	en
dc.rights.accessrights	http://purl.org/eprint/accessRights/OpenAccess	en
pubs.subtype	Article	en
pubs.elements-id	456126	en
pubs.org-id	Science	en
pubs.org-id	School of Computer Science	en
dc.identifier.eissn	1943-5886	en
pubs.record-created-at-source-date	2015-01-28	en