Elementary differences between the degrees of unsolvability and degrees of compressibility

DOI10.1016/J.APAL.2009.11.004MaRDI QIDQ636334zbMATH OpenOpenAlexFDO

Authors 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

elementary equivalencedegrees of unsolvabilitydegrees of compressibilityminimal pairs

Mathematics Subject Classification ID

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

Recommendations

• Incompleteness, approximation and relative randomness
• scientific article; zbMATH DE number 4087652
• Randomness, lowness and degrees
• scientific article; zbMATH DE number 1048044
• Universal computably enumerable sets and initial segment prefix-free complexity

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part I
• A minimal degree less than 0’
• A minimal pair of recursively enumerable degrees
• Almost everywhere domination and superhighness
• Computability and randomness
• Low for random reals and positive-measure domination
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Lowness notions, measure and domination
• Lowness properties and randomness
• Non-cupping, measure and computably enumerable splittings
• Randomness, lowness and degrees
• Relative randomness and cardinality
• Tracing and domination in the Turing degrees
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees

Cited in

(5)

• Universal computably enumerable sets and initial segment prefix-free complexity
• Low upper bounds in the LR degrees
• Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Kolmogorov complexity of initial segments of sequences and arithmetical definability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q636334)