Conditional Kolmogorov Complexity and Universal Probability

Paul M. B. Vitanyi

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…