Article contents
CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS
Published online by Cambridge University Press: 25 June 2014
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.
- Type
- Articles
- Information
- Copyright
- Copyright © The Association for Symbolic Logic 2014
References
REFERENCES
- 4
- Cited by