Incompleteness, approximation and relative randomness

DOI10.3233/COM-12014MaRDI QIDQ4904462zbMATH OpenOpenAlexFDO

Authors Anthony Morphett

Publication date 30 January 2013

Published in Computability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/com-12014

zbMATH Keywords

Kolmogorov complexityincompletenesscomputably enumerable degreesrelative randomnessMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Recursively (computably) enumerable sets and degrees (03D25)

Recommendations

• Randomness, lowness and degrees
• Low upper bounds in the LR degrees
• Working with the LR Degrees
• Compactness arguments with effectively closed sets for the study of relative randomness
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees

Cited in

(8)

• Relative randomness and cardinality
• Elementary differences between the degrees of unsolvability and degrees of compressibility
• Low upper bounds in the LR degrees
• Working with the LR Degrees
• Oreals with \(\Delta_2^0\)-bounded complexity and compressive power
• Randomness, lowness and degrees
• Prompt enumerations and relative randomness
• Compactness arguments with effectively closed sets for the study of relative randomness

This page was built for publication: Incompleteness, approximation and relative randomness

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