Undecidability of the structure of the Solovay degrees of c.e. reals

DOI10.1016/j.jcss.2007.01.002zbMath1115.03046OpenAlexW2087333392MaRDI QIDQ881596

Geoff LaForte, Denis R. Hirschfeldt, Rodney G. Downey

Publication date: 30 May 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.01.002

zbMATH Keywords

randomnesscomputably enumerable realsSolovay reducibility

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (1)

Universal computably enumerable sets and initial segment prefix-free complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lattice-theoretic decision problems in universal algebra
• Undecidability results for low complexity time classes
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• Calibrating Randomness
• Decidability and Boolean representations
• A Theory of Program Size Formally Identical to Information Theory
• Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras
• The definition of random sequences
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Undecidability of the structure of the Solovay degrees of c.e. reals