Lowness for the class of random sets

DOI10.2307/2586785zbMath0954.68080MaRDI 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 theory; relativized randomness; Kolmogorov-Martin-Löf randomness

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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