Characterizing strong randomness via Martin-Löf randomness

DOI10.1016/j.apal.2011.08.006zbMath1251.03048MaRDI QIDQ409318

Liang Yu

Publication date: 13 April 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.08.006

zbMATH Keywords

Kolmogorov complexity; Martin-Löf randomness

Mathematics Subject Classification ID

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

03D32: Algorithmic randomness and dimension

Related Items

Two more characterizations of \(K\)-triviality, Defining a randomness notion via another

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Randomness notions and partial relativization
• Low upper bounds in the LR degrees
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• An extension of van Lambalgen's theorem to infinitely many relative 1-random reals
• Lowness properties and randomness
• Lowness notions, measure and domination
• Algorithmic Randomness and Complexity
• Initial Segment Complexities of Randomness Notions
• Lowness and nullsets
• Randomness and Computability: Open Questions
• On initial segment complexity and degrees of randomness
• Every sequence is reducible to a random one
• Relativizations of randomness and genericity notions