There is no SW-complete c.e. real

DOI10.2178/JSL/1102022216MaRDI QIDQ5311772zbMATH OpenOpenAlexFDO

Authors Liang Yu, Decheng Ding

Publication date 29 August 2005

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2178/jsl/1102022216

zbMATH Keywords

computably enumerable real numbersKolmogorov complexityrandom realsstrongly weak truth table reducibility

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Some properties of sw-reducibility
• The Kolmogorov complexity of random reals
• There is an Sw-Cuppable Strongly c.e. Real
• A characterization of c. e. random reals

Cites work

• Algorithmic Complexity and Randomness: Recent Developments
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)

Cited in

(19)

• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Randomness and reducibility
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• The ibT degrees of computably enumerable sets are not dense
• Relative randomness and real closed fields
• Calibrating Randomness
• Structures of some strong reducibilities
• The method of the Yu–Ding Theorem and its application
• Universal computably enumerable sets and initial segment prefix-free complexity
• Working with strong reducibilities above totally -c.e. and array computable degrees
• There is an Sw-Cuppable Strongly c.e. Real
• Some properties of sw-reducibility
• A characterization of c. e. random reals
• The computable Lipschitz degrees of computably enumerable sets are not dense
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Extending CL-reducibility on array noncomputable degrees
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Randomness and the linear degrees of computability

This page was built for publication: There is no SW-complete c.e. real

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