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

DOI10.1090/S0002-9947-09-04910-1MaRDI QIDQ5189151zbMATHFDO

Authors George Barmpalias, Noam Greenberg, 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)

Recommendations

• A c.e. weak truth table degree which is array noncomputable and r-maximal
• On the degree structure of equivalence relations under computable reducibility
• T-Degrees, Jump Classes, and Strong Reducibilities
• New Computational Paradigms
• Maximality and collapse in the hierarchy of \(\alpha\)-c.a. degrees

Cites work

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

Cited in

(16)

• Bounded randomness
• On the strongly bounded Turing degrees of the computably enumerable sets
• Computing halting probabilities from other halting probabilities
• A c.e. weak truth table degree which is array noncomputable and r-maximal
• A hierarchy of computably enumerable degrees
• Hierarchy of Computably Enumerable Degrees II
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• Lowness for bounded randomness
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Maximality and collapse in the hierarchy of \(\alpha\)-c.a. degrees
• A Note on the Differences of Computably Enumerable Reals
• Reductions between types of numberings
• Theory and Applications of Models of Computation
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

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

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