Strong jump-traceability. I: The computably enumerable case

DOI10.1016/j.aim.2007.09.008zbMath1134.03026MaRDI 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

computability; computably enumerable; Turing degree; Martin-Löf random; \(K\)-trivial; strongly jump-traceable

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D80: Applications of computability and recursion theory

03D25: Recursively (computably) enumerable sets and degrees

Related Items

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

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