New Computational Paradigms

DOI10.1007/B136981MaRDI QIDQ5717034zbMATH OpenOpenAlexFDO

Authors George Barmpalias

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b136981

Mathematics Subject Classification ID

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

Recommendations

• A c.e. real that cannot be sw-computed by any \(\Omega\) number
• Minimal weak truth table degrees and computably enumerable Turing degrees
• A c.e. weak truth table degree which is array noncomputable and r-maximal
• There is an Sw-Cuppable Strongly c.e. Real
• Some properties of sw-reducibility

Cited in

(17)

• A c.e. weak truth table degree which is array noncomputable and r-maximal
• Maximal pairs of computably enumerable sets in the computably Lipschitz degrees
• Where join preservation fails in the bounded Turing degrees of c.e. sets
• Strong jump-traceability. I: The computably enumerable case
• The ibT degrees of computably enumerable sets are not dense
• Hypersimplicity and semicomputability in the weak truth table degrees
• sQ₁-degrees of computably enumerable sets
• On the strongly bounded Turing degrees of the computably enumerable sets
• Structures of some strong reducibilities
• Universal computably enumerable sets and initial segment prefix-free complexity
• Working with strong reducibilities above totally -c.e. and array computable degrees
• Some properties of sw-reducibility
• Every incomplete computably enumerable truth-table degree is branching
• The computable Lipschitz degrees of computably enumerable sets are not dense
• Maximal pairs of c.e. reals in the computably Lipschitz degrees
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Randomness and the linear degrees of computability

This page was built for publication: New Computational Paradigms

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