Randomness, lowness and degrees

DOI10.2178/jsl/1208359060zbMath1145.03020OpenAlexW2159344545MaRDI QIDQ3503755

Andrew E. M. Lewis, George Barmpalias, Mariya Ivanova Soskova

Publication date: 9 June 2008

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.516.8854

zbMATH Keywords

computably enumerable degreeTuring degreeLR degreeoracle Martin-Löf test

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28)

Related Items

Randomness notions and partial relativization ⋮ Low upper bounds in the LR degrees ⋮ Oscillation in the initial segment complexity of random reals ⋮ Elementary differences between the degrees of unsolvability and degrees of compressibility ⋮ MASS PROBLEMS AND HYPERARITHMETICITY ⋮ \(\Pi_1^0 \) classes, LR degrees and Turing degrees ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Non-cupping, measure and computably enumerable splittings ⋮ 𝐾-trivial degrees and the jump-traceability hierarchy ⋮ Chaitin's halting probability and the compression of strings using oracles ⋮ Randomness and lowness notions via open covers

Cites Work

• Unnamed Item
• Classical recursion theory. Vol. II
• Lowness properties and randomness
• Simple Proofs of Some Theorems on High Degrees of Unsolvability
• A Cappable Almost Everywhere Dominating Computably Enumerable Degree
• Lowness for the class of random sets
• Almost everywhere domination and superhighness
• Low for random reals and positive-measure domination
• Degrees of Unsolvability. (AM-55)