Lowness for the class of random sets

DOI10.2307/2586785zbMath0954.68080OpenAlexW2032484393MaRDI QIDQ4948515

Antonín Kučera, Sebastiaan A. Terwijn

Publication date: 28 January 2001

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2586785

zbMATH Keywords

algorithmic information theoryrelativized randomnessKolmogorov-Martin-Löf randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

On Kurtz randomness, 2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09, Cupping with random sets, CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS, COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS, Random non-cupping revisited, Randomness notions and partial relativization, Lowness and logical depth, Randomness, lowness and degrees, On initial segment complexity and degrees of randomness, Characterizing the strongly jump-traceable sets via randomness, On the number of infinite sequences with trivial initial segment complexity, Truth-table Schnorr randomness and truth-table reducible randomness, Randomness, relativization and Turing degrees, Strong jump-traceability. I: The computably enumerable case, Trivial Reals, Mass Problems and Randomness, Benign cost functions and lowness properties, Tracing and domination in the Turing degrees, Randomness and lowness notions via open covers, 2009 North American Annual Meeting of the Association for Symbolic Logic, Lowness and nullsets, Calibrating Randomness, Non-cupping and randomness, Lowness properties and randomness, Unified characterizations of lowness properties via Kolmogorov complexity

Cites Work

• On relative randomness
• Subsequences of normal sequences
• Every sequence is reducible to a random one
• The definition of random sequences