There is no SW-complete c.e. real

DOI10.2178/jsl/1102022216zbMath1070.03028OpenAlexW2081107054MaRDI QIDQ5311772

Liang Yu, Ding, Decheng

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

Kolmogorov complexityrandom realscomputably enumerable real numbersstrongly weak truth table reducibility

Mathematics Subject Classification ID

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

Related Items

Randomness and reducibility, Randomness and the linear degrees of computability, Non-low\(_2\)-ness and computable Lipschitz reducibility, Maximal pairs of computably enumerable sets in the computably Lipschitz degrees, The computable Lipschitz degrees of computably enumerable sets are not dense, Maximal pairs of c.e. reals in the computably Lipschitz degrees, Structures of Some Strong Reducibilities, Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees, The ibT degrees of computably enumerable sets are not dense, A uniform version of non-\(\mathrm{low}_{2}\)-ness, The method of the Yu–Ding Theorem and its application, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Calibrating Randomness

Cites Work

• Unnamed Item
• Algorithmic Complexity and Randomness: Recent Developments