Characterizing strong randomness via Martin-Löf randomness

DOI10.1016/J.APAL.2011.08.006zbMath1251.03048OpenAlexW2015779758MaRDI 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 complexityMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (2)

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

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

This page was built for publication: Characterizing strong randomness via Martin-Löf randomness