Conditional Kolmogorov complexity and universal probability
The Coding Theorem of L.A. Levin connects unconditional prefix Kolmogorov complexity with the universal semiprobability mass function. There are conditional versions referred to in several publications but as yet there exist no written proofs. Under the classic definition of conditional probability, there is no conditional version of the Coding Theorem. We give the appropriate definitions and provide complete proofs of the conditional version of the Coding Theorem.
conditional kolmogorov complexity definitions of conditional probability conditional universal probability coding theorem for conditional versions