Strong jump-traceability. I: The computably enumerable case

DOI10.1016/j.aim.2007.09.008zbMath1134.03026OpenAlexW2171441747MaRDI QIDQ2474313

Noam Greenberg, Rodney G. Downey, Peter A. Cholak

Publication date: 5 March 2008

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2007.09.008

zbMATH Keywords

computabilitycomputably enumerableTuring degreeMartin-Löf random\(K\)-trivialstrongly jump-traceable

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (21)

Strengthening prompt simplicity ⋮ Randomness, Computation and Mathematics ⋮ 2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09 ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ STRONG JUMP-TRACEABILITY ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ A \(K\)-trivial set which is not jump traceable at certain orders ⋮ MASS PROBLEMS AND HYPERARITHMETICITY ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Computably enumerable sets below random sets ⋮ A semilattice generated by superlow computably enumerable degrees ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ On arithmetical level of the class of superhigh sets ⋮ On strongly jump traceable reals ⋮ A random set which only computes strongly jump-traceable c.e. sets ⋮ Lowness properties and approximations of the jump ⋮ Lowness for Demuth Randomness ⋮ Benign cost functions and lowness properties ⋮ 𝐾-trivial degrees and the jump-traceability hierarchy ⋮ 2009 North American Annual Meeting of the Association for Symbolic Logic ⋮ Inherent enumerability of strong jump-traceability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Strong jump-traceability. II: \(K\)-triviality
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Information-theoretic characterizations of recursive infinite strings
• Process complexity and effective random tests
• Lowness properties and approximations of the jump
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Lowness properties and randomness
• Computational randomness and lowness
• A Refinement of Lown and Highn for the R.E. Degrees
• Algorithmic Randomness and Complexity
• Lowness and nullsets
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Non-cupping and randomness
• On initial segment complexity and degrees of randomness
• Recursively enumerable sets and degrees
• Lowness for the class of random sets
• Using random sets as oracles
• Schnorr randomness
• Lowness for the Class of Schnorr Random Reals
• A variant of the Kolmogorov concept of complexity

This page was built for publication: Strong jump-traceability. I: The computably enumerable case