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

computably enumerable degreesincompletenessKolmogorov complexityMartin-Löf randomnessrelative randomness

Mathematics Subject Classification ID

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

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)

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

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)