Randomness, lowness and degrees

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

George Barmpalias, Andrew E. M. Lewis, 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 degree; Turing degree; LR degree; oracle Martin-Löf test

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

03D30: Other degrees and reducibilities in computability and recursion theory

03D28: Other Turing degree structures

Related Items

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, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Randomness and lowness notions via open covers, \(\Pi_1^0 \) classes, LR degrees and Turing degrees, Chaitin's halting probability and the compression of strings using oracles, MASS PROBLEMS AND HYPERARITHMETICITY, Non-cupping, measure and computably enumerable splittings, 𝐾-trivial degrees and the jump-traceability hierarchy

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)