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

DOI10.1090/S0002-9947-09-04910-1zbMATH Open1192.03014MaRDI QIDQ5189151FDOQ5189151

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)

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

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)

Cites Work

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

Cited In (14)

• Computing halting probabilities from other halting probabilities
• Lowness for bounded randomness
• A Note on the Differences of Computably Enumerable Reals
• On the Strongly Bounded Turing Degrees of the Computably Enumerable Sets
• Bounded randomness
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• A uniform version of non-\(\mathrm{low}_{2}\)-ness
• 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
• A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES
• Non-low\(_2\)-ness and computable Lipschitz reducibility
• Hierarchy of Computably Enumerable Degrees II

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)