Characterising the Martin-Löf random sequences using computably enumerable sets of measure one

DOI10.1016/j.ipl.2004.06.016zbMath1173.68540OpenAlexW2083176123MaRDI QIDQ834927

George Davie

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.06.016

zbMATH Keywords

computational complexityKolmogorov complexityprobability lawMartin-Löf randomcompressibility coefficient

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Foundations of probability theory (60A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Calibrating Randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Identifying randomness given by high descriptive complexity
• A Theory of Program Size Formally Identical to Information Theory
• Kolmogorov complexity and symmetric relational structures
• Descriptive Complexity and Reflective Properties of Combinatorial Configurations
• Complexity oscillations in infinite binary sequences
• The definition of random sequences