Conditional Kolmogorov complexity and universal probability

DOI10.1016/J.TCS.2013.07.009MaRDI QIDQ391323zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paul M. B. Vitányi

Publication date 10 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0983

zbMATH Keywords

coding theorem for conditional versionsconditional Kolmogorov complexityconditional universal probabilitydefinitions of conditional probability

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Axioms; other general questions in probability (60A05)

Abstract: The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. There are conditional versions referred to in several publications but as yet there exist no written proofs in English. Here we provide those proofs. They use a different definition than the standard one for the conditional version of the discrete universal distribution. Under the classic definition of conditional probability, there is no conditional version of the Coding Theorem.

Recommendations

• Proofs of conservation inequalities for Levin's notion of mutual information of 1974
• The Kolmogorov complexity, universal distribution, and coding theorem for generalized length functions
• Logical operations and Kolmogorov complexity

Cites work

• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 3557755 (Why is no real title available?)
• A Mathematical Theory of Communication
• An introduction to Kolmogorov complexity and its applications
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(8)

• Axiomatizing Kolmogorov complexity
• Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov)
• The proof of Levin's conjecture
• On the computability of conditional probability
• Prefix-free and prefix-correct complexities with compound conditions
• Conditional probabilities and van Lambalgen's theorem revisited
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Towards an axiomatic system for Kolmogorov complexity

This page was built for publication: Conditional Kolmogorov complexity and universal probability

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