Increasing the gap between descriptional complexity and algorithmic probability

DOI10.1090/S0002-9947-2011-05315-8MaRDI QIDQ3093481zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the relation between descriptional complexity and algorithmic probability
• A coding theorem for enumerable output machines
• Inequalities for space-bounded Kolmogorov complexity
• Invariance and Universality of Complexity

Cites work

• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications. 2nd ed
• Computability and randomness
• Degrees of monotone complexity
• Incompleteness theorems for random reals
• On the relation between descriptional complexity and algorithmic probability
• Process complexity and effective random tests
• 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

Cited in

(3)

• On the relation between descriptional complexity and algorithmic probability
• A generalized characterization of algorithmic probability
• Randomness, computation and mathematics

This page was built for publication: Increasing the gap between descriptional complexity and algorithmic probability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093481)