Increasing the gap between descriptional complexity and algorithmic probability

DOI10.1090/S0002-9947-2011-05315-8zbMath1257.68084OpenAlexW2018578203MaRDI QIDQ3093481

Adam R. Day

Publication date: 17 October 2011

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9947-2011-05315-8

zbMATH Keywords

algorithmic probabilitycoding theoremGács theorem

Mathematics Subject Classification ID

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

Related Items

Randomness, Computation and Mathematics ⋮ A generalized characterization of algorithmic probability

Cites Work

• On the relation between descriptional complexity and algorithmic probability
• Incompleteness theorems for random reals
• Process complexity and effective random tests
• Algorithmic Randomness and Complexity
• Degrees of monotone complexity
• Relations between varieties of kolmogorov complexities
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• Unnamed Item
• Unnamed Item