Incompleteness, approximation and relative randomness

DOI10.3233/COM-12014zbMATH Open1282.03020OpenAlexW1949710668MaRDI QIDQ4904462FDOQ4904462

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

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

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)

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)