Kolmogorov entropy in the context of computability theory

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

zbMATH Keywords

completenessseparabilityKolmogorov entropy

Mathematics Subject Classification ID

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

Related Items (8)

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

This page was built for publication: Kolmogorov entropy in the context of computability theory