A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law

DOI10.1016/0020-0190(95)00201-4zbMath0900.68272OpenAlexW2012525333MaRDI QIDQ672725

Marius Zimand

Publication date: 28 February 1997

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

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00201-4

zbMATH Keywords

Kolmogorov complexityLogical definabilityProbability asymptotics

Mathematics Subject Classification ID

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

Cites Work

• Optimization, approximation, and complexity classes
• Infinitary logics and 0-1 laws
• The Kolmogorov expressive power of Boolean query languages
• Probabilities on finite models
• On Languages Reducible to Algorithmically Random Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law