Low upper bounds in the LR degrees
From MaRDI portal
Publication:409325
DOI10.1016/j.apal.2011.10.001zbMath1247.03073MaRDI QIDQ409325
Publication date: 13 April 2012
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2011.10.001
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D25: Recursively (computably) enumerable sets and degrees
03D30: Other degrees and reducibilities in computability and recursion theory
03D32: Algorithmic randomness and dimension
Related Items
Characterizing strong randomness via Martin-Löf randomness, Defining a randomness notion via another
Cites Work
- Unnamed Item
- Elementary differences between the degrees of unsolvability and degrees of compressibility
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
- Lowness properties and randomness
- Chaitin's halting probability and the compression of strings using oracles
- Randomness, lowness and degrees
- The importance of Π10 classes in effective randomness
- Almost everywhere domination and superhighness
- Low for random reals and positive-measure domination