Conditional Kolmogorov Complexity and Universal Probability

Open Access
Authors
Publication date 05-06-2012
Number of pages 18
Publisher Ithaca, NY: ArXiv
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract
The conditional in conditional Kolmogorov complexity commonly is taken to be a finite binary string. The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the discrete universal distribution. The least upper semicomputable code-length is up to a constant equal to the negative logarithm of the greatest lower semicomputable probability mass function. We investigate conditional versions of the Coding Theorem for singleton and joint probability distributions under alternative definitions. No conditional Coding Theorem holds in the singleton case, in the joint case under the customary definition of conditional probability, but it does hold in the joint case under an alternative definition.
Document type Working paper
Note Version 2 (2013) also available on ArXiv.org.
Language English
Related publication Conditional Kolmogorov complexity and universal probability
Published at https://arxiv.org/abs/1206.0983v1
Downloads
1206.0983v1 (Submitted manuscript)
Permalink to this page
Back