Increasing the gap between descriptional complexity and algorithmic probability
From MaRDI portal
Publication:3093481
DOI10.1090/S0002-9947-2011-05315-8zbMath1257.68084MaRDI QIDQ3093481
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
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- 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