Computational randomness and lowness
It is shown that there exist uncountably many sets that are low for the class \(C\) of Schnorr random sets (also called recursively random sets). This is a purely recursion-theoretic characterization of these sets. Lowness of a set \(A\) with respect to some class of sets \(C\) means that \(C\), relative to \(A\), is included in \(C\). This is a useful concept both in recursion theory and structural complexity. This result contrasts with a result of \textit{A. Kucera} and \textit{S. A. Terwijn} [J. Symb. Log. 64, 1396-1402 (1999; Zbl 0954.68080)] on sets which are low for the class of Martin-Löf random sets.
- On Kurtz randomness
- Computable analogs of cardinal characteristics: prediction and rearrangement
- Unified characterizations of lowness properties via Kolmogorov complexity
- Integer valued betting strategies and Turing degrees
- Schnorr triviality and its equivalent notions
- Lowness for difference tests
- Strong jump-traceability. I: The computably enumerable case
- Lowness properties and approximations of the jump
- Lowness properties and randomness
- Reducibilities relating to Schnorr randomness
- Characterizing lowness for Demuth randomness
- Asymptotic density and the theory of computability: a partial survey
- Lowness, Randomness, and Computable Analysis
- Benign cost functions and lowness properties
- 2009–2010 Winter Meeting of the Association for Symbolic Logic
- Asymptotic density, computable traceability, and 1-randomness
- Randomness and Computability: Open Questions
- Calibrating Randomness
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM
- Lowness for Demuth Randomness
- Counting the changes of random \({\Delta}^0_2\) sets
- Hyperimmune-free degrees and Schnorr triviality
- 𝐾-trivial degrees and the jump-traceability hierarchy
- Lowness for Kurtz randomness
- Strong jump-traceability. II: K-triviality
- Randomness notions and partial relativization
- Natural factors of the Muchnik lattice capturing IPC
- Computing with Very Weak Random Sources
- Randomness of Low-Order Bits in Random Number Generators
- A \(K\)-trivial set which is not jump traceable at certain orders
- Strong jump-traceability
- Trivial Reals
- Schnorr Trivial Reals: A construction
- Lowness properties of reals and hyper-immunity
- Lowness for the class of random sets
- The complexity of recursive splittings of random sets
- Relationships between computability-theoretic properties of problems
- Covering the recursive sets
- Lowness for isomorphism, countable ideals, and computable traceability
- Low for random reals and positive-measure domination
- Schnorr randomness
- Inherent enumerability of strong jump-traceability
- Randomness, relativization and Turing degrees
- SOME CONSEQUENCES OF AND
- Higher Kurtz randomness
- Some more results on relativized Chaitin's
- Tracing and domination in the Turing degrees
- Randomness and lowness notions via open covers
- Lowness for genericity
- On strongly jump traceable reals
- Schnorr trivial reals: a construction
- Lowness of higher randomness notions
- Turing degrees of reals of positive effective packing dimension
- Relativized Schnorr tests with universal behavior
This page was built for publication: Computational randomness and lowness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2758053)
