Lowness properties and approximations of the jump

DOI10.1016/j.apal.2007.11.002zbMath1137.03025MaRDI QIDQ2478546

Frank Stephan, André Nies, Santiago Figueira

Publication date: 28 March 2008

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2007.11.002

zbMATH Keywords

lowness; strong jump-traceability; well-approximation of the jump

Mathematics Subject Classification ID

03D35: Undecidability and degrees of sets of sentences

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

03D25: Recursively (computably) enumerable sets and degrees

Related Items

STRONG JUMP-TRACEABILITY, Inherent enumerability of strong jump-traceability, Strong jump-traceability. II: \(K\)-triviality, Computably enumerable sets below random sets, Characterizing the strongly jump-traceable sets via randomness, Upper bounds on ideals in the computably enumerable Turing degrees, Demuth randomness and computational complexity, Strong jump-traceability. I: The computably enumerable case, DEMUTH’S PATH TO RANDOMNESS, CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS, A random set which only computes strongly jump-traceable c.e. sets, Benign cost functions and lowness properties, MASS PROBLEMS AND HYPERARITHMETICITY, Lowness for Demuth Randomness, 𝐾-trivial degrees and the jump-traceability hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness and universal machines
• Classical recursion theory. The theory of functions and sets of natural numbers
• Information-theoretic characterizations of recursive infinite strings
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and randomness
• Computational randomness and lowness
• A Refinement of Lown and Highn for the R.E. Degrees
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• A Theory of Program Size Formally Identical to Information Theory