Demuth randomness and computational complexity
From MaRDI portal
Publication:639659
DOI10.1016/j.apal.2011.01.004zbMath1223.03026OpenAlexW1989278258MaRDI QIDQ639659
Publication date: 22 September 2011
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.2011.01.004
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)
Related Items (15)
Demuth’s Path to Randomness ⋮ CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS ⋮ JSL volume 79 issue 2 Cover and Front matter ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ Randomness notions and partial relativization ⋮ STRONG JUMP-TRACEABILITY ⋮ Continuous randomness via transformations of 2-random sequences ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Inherent enumerability of strong jump-traceability ⋮ Reductions between types of numberings ⋮ Denjoy, Demuth and density
Cites Work
- Randomness notions and partial relativization
- Characterizing the strongly jump-traceable sets via randomness
- Lowness properties and approximations of the jump
- Degrees of members of \(\Pi_ 1^ 0\) classes
- Lowness properties and randomness
- A random set which only computes strongly jump-traceable c.e. sets
- Benign cost functions and lowness properties
- Randomness and Computability: Open Questions
- Every sequence is reducible to a random one
- Mass problems and almost everywhere domination
- Using random sets as oracles
- Computability and Randomness
- ∏ 0 1 Classes and Degrees of Theories
- Randomness, relativization and Turing degrees
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Demuth randomness and computational complexity