Using random sets as oracles

DOI10.1112/JLMS/JDM041MaRDI QIDQ5308172zbMATH OpenOpenAlexFDO

Authors Denis R. Hirschfeldt, André Nies, 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

zbMATH Keywords

base for 1-randomnessrandom reals

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited in

(40)

• On independent random oracles
• Two more characterizations of \(K\)-triviality
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Unified characterizations of lowness properties via Kolmogorov complexity
• Schnorr triviality and its equivalent notions
• Strong jump-traceability. I: The computably enumerable case
• Denjoy, Demuth and density
• Computuing K-trivial sets by incomplete random sets
• K-trivial, K-low and MLR-low sequences: a tutorial
• Lowness, Randomness, and Computable Analysis
• Some Questions in Computable Mathematics
• Coarse reducibility and algorithmic randomness
• Truth-table Schnorr randomness and truth-table reducible randomness
• A random set which only computes strongly jump-traceable c.e. sets
• Difference randomness
• Benign cost functions and lowness properties
• Cupping with random sets
• Closure of resource-bounded randomness notions under polynomial-time permutations
• Non-cupping and randomness
• Schnorr trivial sets and truth-table reducibility
• Lowness for Demuth Randomness
• Low upper bounds of ideals
• Computably enumerable sets below random sets
• Characterizing the strongly jump-traceable sets via randomness
• Strong jump-traceability
• A computable analysis of majorizing martingales
• scientific article; zbMATH DE number 7204368 (Why is no real title available?)
• Computing from projections of random points
• Continuous higher randomness
• Low for random reals and positive-measure domination
• Turing incomparability in Scott sets
• Density-1-bounding and quasiminimality in the generic degrees
• On very high degrees
• Inherent enumerability of strong jump-traceability
• A measure-theoretic proof of Turing incomparability
• Upper bounds on ideals in the computably enumerable Turing degrees
• Demuth randomness and computational complexity
• Martin-Löf reducibility and cost functions
• Calculus of cost functions
• Randomness and universal machines

This page was built for publication: Using random sets as oracles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5308172)