Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees

DOI10.1090/S0002-9947-09-04910-1zbMath1192.03014MaRDI QIDQ5189151

Noam Greenberg, George Barmpalias, Rodney G. Downey

Publication date: 8 March 2010

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

zbMATH Keywords

reducibilityhypersimple setcomputable degree

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (13)

Bounded Randomness ⋮ Non-low\(_2\)-ness and computable Lipschitz reducibility ⋮ Maximal pairs of computably enumerable sets in the computably Lipschitz degrees ⋮ On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets ⋮ A Note on the Differences of Computably Enumerable Reals ⋮ Maximal pairs of c.e. reals in the computably Lipschitz degrees ⋮ A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES ⋮ Lowness for bounded randomness ⋮ Computing halting probabilities from other halting probabilities ⋮ A uniform version of non-\(\mathrm{low}_{2}\)-ness ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Reductions between types of numberings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness and the linear degrees of computability
• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Turing degrees of reals of positive effective packing dimension
• Classical recursion theory. The theory of functions and sets of natural numbers
• Randomness and reducibility
• The ibT degrees of computably enumerable sets are not dense
• Hypersimplicity and semicomputability in the weak truth table degrees
• Randomness and Recursive Enumerability
• Kolmogorov complexity and the Recursion Theorem
• Approximation representations for reals and their wtt‐degrees
• Algorithmic Randomness and Complexity
• Computability Results Used in Differential Geometry
• Random reals and Lipschitz continuity
• TOTALLY ω-COMPUTABLY ENUMERABLE DEGREES AND BOUNDING CRITICAL TRIPLES
• Classifying model-theoretic properties
• The atomic model theorem and type omitting
• Every sequence is reducible to a random one
• Bounded Immunity and Btt-Reductions
• On the construction of effectively random sets
• There is no SW-complete c.e. real
• Π₁⁰ classes and strong degree spectra of relations
• Post's Programme for the Ershov Hierarchy
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Logical Approaches to Computational Barriers
• Logical Approaches to Computational Barriers
• Theory and Applications of Models of Computation

This page was built for publication: Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees