The computable Lipschitz degrees of computably enumerable sets are not dense

DOI10.1016/J.APAL.2010.06.008MaRDI QIDQ636391zbMATH OpenOpenAlexFDO

Authors Adam R. Day

Publication date 26 August 2011

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2010.06.008

zbMATH Keywords

algorithmic information theorycomputable Lipschitz degreescomputably enumerable setsdensitySolovay degrees

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• The ibT degrees of computably enumerable sets are not dense
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• sQ₁-degrees of computably enumerable sets
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• Non-low\(_2\)-ness and computable Lipschitz reducibility
• The computably enumerable degrees are locally non-cappable
• On the strongly bounded Turing degrees of the computably enumerable sets
• The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees
• The nonlow computably enumerable degrees are not invariant in \(\mathcal{E}\)
• Strong noncuppability in low computably enumerable degrees

Cites work

• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Algorithmic randomness and complexity.
• Computability and randomness
• Computability Results Used in Differential Geometry
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• New Computational Paradigms
• Random reals and Lipschitz continuity
• Randomness and reducibility
• The ibT degrees of computably enumerable sets are not dense
• The recursively enumerable degrees are dense
• The weak truth table degrees of recursively enumerable sets
• There is no SW-complete c.e. real

Cited in

(10)

• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• Where join preservation fails in the bounded Turing degrees of c.e. sets
• The ibT degrees of computably enumerable sets are not dense
• On the strongly bounded Turing degrees of the computably enumerable sets
• Random reals and Lipschitz continuity
• Dense computability, upper cones, and minimal pairs
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Compression of enumerations and gain
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

This page was built for publication: The computable Lipschitz degrees of computably enumerable sets are not dense

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