Characterizing lowness for Demuth randomness

Journal of Symbolic Logic 79 (2):526-560 (2014)
  Copy   BIBTEX

Abstract

We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15]. 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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Analytics

Added to PP
2016-06-30

Downloads
17 (#843,162)

6 months
5 (#652,053)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.
Strong Jump-Traceability.Noam Greenberg & Dan Turetsky - 2018 - Bulletin of Symbolic Logic 24 (2):147-164.

Add more citations

References found in this work

The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7-12):159-166.
The Degrees of Hyperimmune Sets.Webb Miller & D. A. Martin - 1968 - Mathematical Logic Quarterly 14 (7‐12):159-166.
Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
Lowness properties and approximations of the jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.

View all 11 references / Add more references