Lowness properties and approximations of the jump
From MaRDI portal
Publication:2478546
DOI10.1016/j.apal.2007.11.002zbMath1137.03025OpenAlexW2015069877MaRDI 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
Undecidability and degrees of sets of sentences (03D35) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25)
Related Items (15)
CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ STRONG JUMP-TRACEABILITY ⋮ MASS PROBLEMS AND HYPERARITHMETICITY ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Demuth randomness and computational complexity ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ A random set which only computes strongly jump-traceable c.e. sets ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Lowness for Demuth Randomness ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Benign cost functions and lowness properties ⋮ 𝐾-trivial degrees and the jump-traceability hierarchy ⋮ Inherent enumerability of strong jump-traceability
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
This page was built for publication: Lowness properties and approximations of the jump
