There are 2^{ℵ₀} many 𝐻-degrees in the random reals

DOI10.1090/S0002-9939-04-07417-9MaRDI QIDQ4813660zbMATH OpenFDO

Authors Liang Yu, Decheng Ding

Publication date 13 August 2004

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/S0002-9939-04-07417-9

zbMATH Keywords

\(H\)-degreeprogram-size complexityrandom reals

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Random reals and the relation \(\omega_ 1\to (\omega_ 1,(\alpha:n))^ 2\)
• On the Cardinality of $$ \sum_2^1 $$ Sets of Reals
• The Π₂⁰ enumeration degrees are not dense
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• scientific article; zbMATH DE number 1048046
• A set with barely degree
• The \(n\)-rea enumeration degrees are dense
• From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II
• Partial Randomness and Dimension of Recursively Enumerable Reals
• Random reals à la Chaitin with or without prefix-freeness

Cites work

• Computability-theoretic and proof-theoretic aspects of partial and linear orderings
• Descriptive set theory
• Randomness and recursive enumerability
• Randomness, computability, and density
• The Kolmogorov complexity of random reals

Cited in

(3)

• The Kolmogorov complexity of random reals
• Calibrating Randomness
• On initial segment complexity and degrees of randomness

This page was built for publication: There are 2^{ℵ₀} many 𝐻-degrees in the random reals

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