Kolmogorov entropy in the context of computability theory
From MaRDI portal
Publication:5958279
DOI10.1016/S0304-3975(01)00028-7zbMath0982.68078OpenAlexW2089314015MaRDI QIDQ5958279
Andrej A. Muchnik, Semen Ye. Positselsky
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00028-7
Related Items
Randomness, Computation and Mathematics, On semimeasures predicting Martin-Löf random sequences, Open problems in universal induction \& intelligence, Approximating Kolmogorov complexity, The Complexity of Complexity, Limits on the Computational Power of Random Strings, On the computational power of random strings, What can be efficiently reduced to the Kolmogorov-random strings?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Recursion theoretic properties of frequency computation and bounded queries
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- w tt-Complete Sets are not Necessarily tt-Complete
- On complexity properties of recursively enumerable sets
- A class of enumerable sets
- On the complexity of random strings
- Relations between varieties of kolmogorov complexities
- A note on universal sets
- Recursively enumerable sets of positive integers and their decision problems
