Relative randomness and cardinality
The paper studies the notion of lowness for the class of Martin-Löf random sets. A set \(B\) is low for Martin-Löf random, if every Martin-Löf random set is also Martin-Löf random relative to \(B\). This notion was introduced by \textit{A. Kučera} and \textit{S. A. Terwijn} [J. Symb. Log. 64, No. 4, 1396--1402 (1999; Zbl 0954.68080)]. Here, it is shown that if \(B\) is \(\Delta^0_2\) then \(B\) is low for Martin-Löf random iff \({\mathcal C}^B\) is countable, where \({\mathcal C}^B\) is the class of those sets \(A\) with the property that every set Martin-Löf random relative to \(B\) is also Martin-Löf random relative to \(A\).
- On relative randomness
- Randomness notions and partial relativization
- Randomness relative to Cantor expansions
- Prompt enumerations and relative randomness
- Randomness and recursive enumerability
- Randomness, evenness, and Rényi's index
- Incompleteness, approximation and relative randomness
- Randomness and Solovay degrees
- Relative randomness and real closed fields
- Finite-dimensional randomness
- On the gap between trivial and nontrivial initial segment prefix-free complexity
- Lowness properties and randomness
- Computational randomness and lowness
- Relative randomness for Martin-Löf random sets
- An analogy between cardinal characteristics and highness properties of oracles
- Chaitin's halting probability and the compression of strings using oracles
- Counting the changes of random _2⁰ sets
- Counting the changes of random \({\Delta}^0_2\) sets
- Randomness notions and partial relativization
- Universal computably enumerable sets and initial segment prefix-free complexity
- Lowness for the class of random sets
- Elementary differences between the degrees of unsolvability and degrees of compressibility
- Lowness for bounded randomness
- Kolmogorov complexity of initial segments of sequences and arithmetical definability
- Randomness and lowness notions via open covers
This page was built for publication: Relative randomness and cardinality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q985004)
