Elementary differences between the degrees of unsolvability and degrees of compressibility

DOI10.1016/j.apal.2009.11.004zbMath1227.03054OpenAlexW2072474105MaRDI QIDQ636334

George Barmpalias

Publication date: 26 August 2011

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.2009.11.004

zbMATH Keywords

minimal pairselementary equivalencedegrees of unsolvabilitydegrees of compressibility

Mathematics Subject Classification ID

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

Related Items (4)

Universal computably enumerable sets and initial segment prefix-free complexity ⋮ Low upper bounds in the LR degrees ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tracing and domination in the Turing degrees
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Relative randomness and cardinality
• Lowness properties and randomness
• Lowness notions, measure and domination
• A minimal degree less than 0’
• Randomness, lowness and degrees
• Non-cupping, measure and computably enumerable splittings
• A Theory of Program Size Formally Identical to Information Theory
• Almost everywhere domination and superhighness
• Low for random reals and positive-measure domination
• A minimal pair of recursively enumerable degrees
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• A formal theory of inductive inference. Part I

This page was built for publication: Elementary differences between the degrees of unsolvability and degrees of compressibility