Using random sets as oracles
From MaRDI portal
Publication:5308172
DOI10.1112/jlms/jdm041zbMath1128.03036OpenAlexW2019232231MaRDI QIDQ5308172
André Nies, Denis R. Hirschfeldt, Frank Stephan
Publication date: 27 September 2007
Published in: Journal of the London Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1112/jlms/jdm041
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)
Related Items
Low for random reals and positive-measure domination ⋮ Turing incomparability in Scott sets ⋮ Cupping with random sets ⋮ COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS ⋮ Randomness and universal machines ⋮ STRONG JUMP-TRACEABILITY ⋮ $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial ⋮ DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES ⋮ Computing from projections of random points ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Lowness, Randomness, and Computable Analysis ⋮ A measure-theoretic proof of Turing incomparability ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Demuth randomness and computational complexity ⋮ Some Questions in Computable Mathematics ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ On very high degrees ⋮ Truth-table Schnorr randomness and truth-table reducible randomness ⋮ A random set which only computes strongly jump-traceable c.e. sets ⋮ Two more characterizations of \(K\)-triviality ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Schnorr trivial sets and truth-table reducibility ⋮ Lowness for Demuth Randomness ⋮ Unnamed Item ⋮ Difference randomness ⋮ Benign cost functions and lowness properties ⋮ Low upper bounds of ideals ⋮ Inherent enumerability of strong jump-traceability ⋮ Non-cupping and randomness ⋮ A computable analysis of majorizing martingales ⋮ Unified characterizations of lowness properties via Kolmogorov complexity ⋮ Continuous higher randomness ⋮ Schnorr triviality and its equivalent notions ⋮ Denjoy, Demuth and density ⋮ Closure of resource-bounded randomness notions under polynomial time permutations
