Randomness notions and partial relativization
From MaRDI portal
Publication:375818
DOI10.1007/s11856-012-0012-5zbMath1279.03065MaRDI QIDQ375818
André Nies, Joseph S. Miller, George Barmpalias
Publication date: 1 November 2013
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11856-012-0012-5
reducibility; highness; lowness; Martin-Löf randomness; Schnorr randomness; relativisation; weak randomness
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D32: Algorithmic randomness and dimension
Related Items
Computing from projections of random points, Lowness for effective Hausdorff dimension, Characterizing strong randomness via Martin-Löf randomness, Demuth randomness and computational complexity, Defining a randomness notion via another, JSL volume 79 issue 2 Cover and Front matter
Cites Work
- Unnamed Item
- Demuth randomness and computational complexity
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- Relative randomness and cardinality
- The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
- Information-theoretic characterizations of recursive infinite strings
- Lowness properties and randomness
- Computational randomness and lowness
- Lowness notions, measure and domination
- Randomness, lowness and degrees
- MASS PROBLEMS AND HYPERARITHMETICITY
- Counting the Changes of Random ${\Delta^0_2}$ Sets
- Lowness for Kurtz randomness
- Lowness for the class of random sets
- Almost everywhere domination and superhighness
- Low for random reals and positive-measure domination
- Almost everywhere domination
- A Weakly 2-Random Set That Is Not Generalized Low