Low upper bounds in the LR degrees

DOI10.1016/j.apal.2011.10.001zbMath1247.03073OpenAlexW2034570600MaRDI QIDQ409325

David E. Diamondstone

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

zbMATH Keywords

computability theorylownessrandomnessK-trivials

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items (2)

Defining a randomness notion via another ⋮ Characterizing strong randomness via Martin-Löf randomness

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 Π₁⁰ classes in effective randomness
• Almost everywhere domination and superhighness
• Low for random reals and positive-measure domination

This page was built for publication: Low upper bounds in the LR degrees